Fixed Point

Fixed Point

1. What is this problem about?

The Fixed Point interview question is a search problem involving a sorted array of unique integers. A "fixed point" is an index $i$ such that $arr[i] = i$. You are asked to find the smallest index $i$ that is a fixed point. If no such index exists, you should return -1.

2. Why is this asked in interviews?

Uber and other companies use the Fixed Point coding problem to see if a candidate can recognize an opportunity for Binary Search in a non-obvious context. Since the array is sorted and elements are unique, the difference $arr[i] - i$ is a monotonically non-decreasing function. This property allows you to discard half of the search space in each step, reaching a logarithmic time complexity ($O(\log N)$).

3. Algorithmic pattern used

This problem is a direct application of the Binary Search interview pattern.

1. Pointers: left = 0, right = n - 1.
2. Logic:
   • If arr[mid] == mid, this is a potential answer. However, we need the smallest index, so we record this index and continue searching the left half: ans = mid, right = mid - 1.
   • If arr[mid] < mid, then for all $j < mid$, arr[j] must also be less than $j$ (because the values can't "catch up" to the indices without a larger gap). Move left = mid + 1.
   • If arr[mid] > mid, then for all $j > mid$, arr[j] will always be greater than $j$. Move right = mid - 1.

4. Example explanation

Array: [-10, -5, 2, 3, 7]

1. left=0, right=4, mid=2. arr[2] = 2. Smallest found so far: 2. Search left (right = 1).
2. left=0, right=1, mid=0. arr[0] = -10 < 0. Search right (left = 1).
3. left=1, right=1, mid=1. arr[1] = -5 < 1. Search right (left = 2).
4. Loop ends. Smallest fixed point: 2.

5. Common mistakes candidates make

• Linear Search: Using a single loop ($O(N)$) which is correct but sub-optimal given the "sorted" property.
• Not finding the smallest: Returning the first fixed point found by binary search without checking if a smaller one exists to the left.
• Incorrect condition: Comparing arr[mid] with a target value instead of its own index mid.

6. Interview preparation tip

Binary Search is useful whenever the "error" or "difference" between your current value and a target is monotonic. In this Array interview pattern, the monotonic value is arr[i] - i.