CODEWITHSUNDEEP
arraysbinary-search
Garrick
Garrick

Reputation: 689

Find the next index and last index for a particular index in an array?

Find the next index in the array which is equal to specific element and previous index in the array which is also equal to the specific element ?

Let's take some example: Given array is(Array will contain only elements 5,0 and 6)

5 0 5 5 0 0 5 0 0 0 0 0 6 6 6 0 0 6 0 6 5 5 0

if we take any index say 8 which contains zero. For this index the next element 6 lies at index 12 and last 5 lies at index 6. Similarly, let's take index 2. For this index the next element 6 lies at index 12 and last 5 lies at index 2 only.

My approaches:

  1. I used countfives array which stores the indexes of 5 and countsixes stores the index of 6. It is used in such a way that if any index contains 5 then countfives stores it and if next index stores zero then countfives[i] = countfives[i-1]. Using this for every index I have last 5 and next 6.

  2. I used binary search to find index of next 6 and last 5.

Is there any way this can be done more optimally ?

Upvotes: 1

Views: 123

Answers (1)

Kai O.
Kai O.

Reputation: 166

Looking at the solutions you suggested:

  1. This is definitely the fastest possible lookup time at O(1) since you literally have a full table containing the answers. However, it will take a lot of memory and may have slow insertion times due to having to modify three different arrays.

  2. I don't think this will work, since binary search only works on sorted arrays, and your array is not sorted. However, it could be that you were suggesting the second solution I suggest below.

A couple potential other solutions:

  1. The simplest solution: Worst-case O(n) to iterate forward and backward from your start index until you find the numbers you want. This could be pretty fast if there are 5's and 6's close to the chosen index, since the actual number of indexes we have to check is only the distance the target is away from the start. Most of the time this is probably the most practical option.

  2. Create a sorted array with the indexes of all the fives and sixes (because they're indexes, they'll already be in order). So, fives = [0, 2, 3, 6, 20, 21] and sixes = [12, 13, 14, 17, 18]. We then can have an O(logn) modified binary search through each of these arrays to find the first index greater/less than the original index. While it does take a bit more memory than just operating on the original array, it will be much less than your first solution. It doesn't have the O(1) time, but O(logn) is still very good so you'll have to decide on that tradeoff.

Ultimately, it really depends on whether you value lookup time, insertion time, or memory most.

Upvotes: 1

Related Questions