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;
};

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.

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

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.