LeetCode 1064: Fixed Point

Problem Restatement

We are given a sorted integer array arr with distinct elements.

A fixed point is an index i where arr[i] == i.

Return the smallest fixed point, or -1 if none exists.

The official constraints state that 1 <= arr.length <= 10^4.

Input and Output

Function shape:

def fixedPoint(arr: list[int]) -> int:
    ...

Examples

Example 1:

arr = [-10, -5, 0, 3, 7]

arr[3] = 3. Fixed point at index 3.

Answer: 3.

Example 2:

arr = [0, 2, 5, 8, 17]

arr[0] = 0. Fixed point at index 0.

Answer: 0.

Key Insight

Since the array is sorted and has distinct elements, arr[i] - i is strictly increasing.

A fixed point exists where arr[i] - i == 0.

Binary search on arr[i] - i: find the leftmost index where this is zero.

Edge Cases

• Check the smallest and largest valid search values; off-by-one errors usually appear at the boundaries.
• Decide whether the predicate is looking for the first true value, the last true value, or an exact match.
• When the target is absent, the loop should still terminate and return the problem-specific failure value.

Common Pitfalls

• Do not mix inclusive and half-open bounds inside the same loop.
• Make sure each branch strictly reduces the search interval.

Implementation

class Solution:
    def fixedPoint(self, arr: list[int]) -> int:
        lo, hi = 0, len(arr) - 1
        result = -1

        while lo <= hi:
            mid = (lo + hi) // 2
            if arr[mid] == mid:
                result = mid
                hi = mid - 1
            elif arr[mid] < mid:
                lo = mid + 1
            else:
                hi = mid - 1

        return result

Testing

def run_tests():
    s = Solution()

    assert s.fixedPoint([-10,-5,0,3,7]) == 3
    assert s.fixedPoint([0,2,5,8,17]) == 0
    assert s.fixedPoint([-10,-5,3,4,7,9]) == -1

    print("all tests passed")

run_tests()