Find smallest index that is identical to the value in an array

Question

The task is taken from LeetCode

Given an array A of distinct integers sorted in ascending order, return the smallest index i that satisfies A[i] == i. Return -1 if no such i exists.

Example 1:

Input: [-10,-5,0,3,7]
Output: 3
Explanation: 
// For the given array, A[0] = -10, A[1] = -5, A[2] = 0, A[3] = 3, thus the output is 3.

Example 2:

Input: [0,2,5,8,17]
Output: 0
Explanation: 
// A[0] = 0, thus the output is 0.

Example 3:

Input: [-10,-5,3,4,7,9]
Output: -1
Explanation: 
// There is no such i that A[i] = i, thus the output is -1.

Note:

1 <= A.length < 10^4

-10^9 <= A[i] <= 10^9

My solution

has time complexity of \$O(n)\$ and space complexity of \$O(1)\$. I start to look from the start to the last element. If I find a value that is greater than i, then I can exit early (because there won't be an element that is equal to i anymore). If I find A[i] === i, then I have a result.

Is there a faster solution than the one provided?

/**
 * @param {number[]} A
 * @return {number}
 */
var fixedPoint = function(A) {
 for (let i = 0; i < A.length; i++) {
 if (A[i] > i) { return -1; }
 if (A[i] === i) { return i; }
 }
 return -1;
};

• morbusg: I wonder what's wrong with ary.findIndex((n, i) => n === i)?

Answer 1

I took your previous, invalid solution, and amended it so it does work correctly. So in a way, I am still reviewing your code.

function fixedPoint(data)
{
 const lastIndex = data.length - 1;
 if (data[0] > 0 || data[lastIndex] < 0) return -1;
 var left = 0;
 var right = lastIndex - 1;
 while(left <= right) {
 let middle = Math.floor((left + right) / 2);
 if (data[middle] == middle) {
 while(middle > 0 && data[middle] == middle) middle--;
 return ++middle;
 }
 if (data[middle] > middle) right = middle;
 else if (data[middle] < middle) left = middle;
 }
 return -1;
}

I prefer calling a function a function here, but that's a personal choice.

This is basically a binary search with a small addition to not trip over arrays like:

[-10,-5,0,3,4,5,6,7,8,10].

This little routine first takes care of 2 edge cases: There is no match when the first value is bigger than zero of when the last value is negative. Then it defines two variables, the left and right indexes, within which the solution should be found, or not. At first these indexes span the whole array. On every iteration of the while loop the searchable section of the array is halved, by either assigning the half-way index middle to the left or the right index based on the value in the array at that half-way location. When a match is found, between the index and the value, it walks backwards if there are more matches before the current one.

• KIKO Software: @dfhwze Yes, or when the first item is bigger than zero. I've now added these two edge cases.
• KIKO Software: @dfhwze It will depend on the values in the array. Both binary searches will perform similarly. The question is which walk will, on average, be the longest. I think walking up from the start, as you defined it, will take longer.
• coderodde: Seems to me like worst-case \$\Theta(N)\$.
• KIKO Software: @coderodde Please be more explicit in what you say. What seems to you like what and why?
• KIKO Software: @coderodde: That happens only in the case that there are multiple matches in sequence and we didn't end up on the first one. Do you have a better solution?

Answer 2

Review

Your solution naively walks the array of ascending integers from starting position s = 0. In some situations, this means you are walking tons of negative numbers, knowing they can never match an array index, which is always nonnegative.

Optimization

You could optimize s before walking the array. Since array indices are nonnegative integers, you should skip walking the array where the values are strict negative.

As en example, if input = [-10000, -9999, ..., 0, 1] you just want to check 0 and 1.

The way I would optimize the algorithm:

• determine starting point s
  • if first item is positive: s = 0
  • if last item is strict negative: return -1
  • perform binary search to find s (you want s to hold the first positive integer in the array)
• walk i as from s to end of array
  • on match: return match
  • on array[i]> i: return -1
  • on end reached without match: return -1

Optimized Time Complexity

~\0ドル(\lg m)\$ with m <= n and m being the number of positive integers in the array

• KIKO Software: The same is true for very large numbers. Values bigger than the array is long cannot be the same as an array index. The question is, how do you efficiently find these start and end points? Isn't that basically the same problem as you had before? Why not simply do a binary search for the thing you're actually looking for?
• dfhwze: Good observations. The question is when does it pay off performing binary search for both determining the start and end index to walk? Perhaps the size of the array should also be taken into account. Small arrays probably are better of walking from 0 to end.
• dfhwze: @KIKO Software To answer your first question (1) very large values are short-circuited in the check array[i] > i: return -1
• KIKO Software: Yes, that's true.
• Heinzi: Isn't the worst-case time complexity still O(n), without $lg$? Consider, for example, the array [-1, 0, 1, 2, ..., n-3, n-2].

Answer 3

Here is a simplified version of KIKO Software code, which solves the problem in O(lg(n)) operations.

 function fixedPoint(data)
 {
 const lastIndex = data.length - 1;
 if (lastIndex < 0 || data[0] > 0 || data[lastIndex] < lastIndex) return -1;
 var left = 0;
 var right = lastIndex;
 while(left + 1 < right) {
 let middle = Math.floor((left + right) / 2);
 if (data[middle] >= middle) right = middle;
 else left = middle;
 }
 if(data[left] == left) return left;
 else if (data[right] == right) return right;
 else return -1;
 }

Since we are using binary search all the way we get good worst case behaviour. Also we have ditched the if statement statement for correct answer, and removed another redudant if statement, which reduces the amount of if statements checked from roughly 3.5/iteration to 2 per iteration (remember the while check). I also fixed the problem where if there was no solution and you were left with left and right being just next to each other and left was not a valid solution, then you would enter an infinite loop, as left would be continously assigned from the middle, but the middle was rounded down to the left. Note that this could only happen in the case where left was never moved (first value would be negative and the second value would be 2 or higher).

If you want to go even faster than this, you can try to find a reasonable way to estimate a good middle suggestion. This kind of approach may yeild lower worst-case performance, but you might be able to reach O(lg(lg(n))) average case runtime (I have heard about other algorithms of this type claiming such performance, but I am not familiar with the proofs). Here is example an following:

 function fixedPoint(data)
 {
 const lastIndex = data.length - 1;
 if (lastIndex < 0 || data[0] > 0 || data[lastIndex] < lastIndex) return -1;
 var left = 0;
 var right = lastIndex;
 while(left + 1 < right) {
 let rightWeight = max(left -data[left],1);
 let leftWeight = max(data[right] - right, 1);
 if (rightWeight / 3 > leftWeight ) rightWeight = leftWeight * 3;
 if (leftWeight / 9 > rightWeight ) leftWeight = rightWeight * 9;
 let middle = Math.floor((left * leftWeight + right * rightWeight) / (leftWeight + rightWeight));
 if (data[middle] >= middle) right = middle;
 else left = middle;
 }
 if(data[left] == left) return left;
 else if (data[right] == right) return right;
 else return -1;
 }

The idea in the above is to estimate a good middle point based on the predicted crossover point if we draw a line strait between the left and right. I added a max(weight,1), to ensure that the weights are positive and we do not get stuck. To preserve good performance when the right points are valid candidates, we have put a bound on how far to the right we want our middle guess to be, and to preserve worst-case optimal behaviour a less tight boud on how far to the left we allow our guess to be have also been included. Note that this version may be slower in practice, due to a higher cost of running through each piece of the loop. If you want to use this, then I suggest trying out different values for the bounds on how far to the left or right you allow it to go, and even trying with those bounds turned off entirely.

• greybeard: Code nicely explained externally; put an explanation in the code. This is Code Review: What insightful observation about the code in the question does your answer provide?
• Ninetails: Asside from fixing some errors in the first version, the insightfull observations are mainly ways to increase the performance (worst-case for the first and and average-case for the second).
• greybeard: fixing some errors, increase the performance refers to code from what post?
• Ninetails: Naturally the one KIKO Software wrote, I did mention in the beginning that it was a simplified/modified version of his/her code. Note that the theoretical performance is increased beyond that of the other answers, and the question was specifically for ways to increase performance.
• Mees de Vries: This is the only correct answer here, in the sense that it is the only one that runs in O(log(n)). One more improvement: you can do an early exit when data[lastIndex] < lastIndex, not just when data[lastIndex] < 0. Furthermore I prefer taking right = lastIndex (without the -1), then you can remove the line else if (data[right] == right) return right;.