Is Fixed Point easy or hard?

Fixed Point is categorized as an Easy problem on LeetCode. The brute force solution is straightforward, while the optimal binary search version tests your understanding of monotonic properties in sorted arrays.

Fixed Point Python/Java solution

Most implementations use a standard binary search loop with two pointers (left and right). The same logic works across Python, Java, C++, Go, and TypeScript: compute mid, compare nums[mid] with mid, and adjust the search range accordingly.

How to solve Fixed Point in O(log n)?

Use binary search on the sorted array. Compute mid and compare nums[mid] with mid. If nums[mid] mid, search the left half. When nums[mid] == mid, record the index and continue searching left to ensure the smallest fixed point.

What is the best approach for Fixed Point?

Binary search is the optimal approach because the array is sorted and contains distinct integers. By analyzing the monotonic behavior of nums[i] - i, you can discard half the search space each step. This results in O(log n) time and O(1) extra space, which is significantly faster than scanning the entire array.

Is Fixed Point asked at Google/Amazon/Meta?

Fixed Point is a classic binary search variation that appears in technical interview practice sets and algorithm courses. Similar problems involving monotonic functions and index-value relationships are common at companies like Google, Amazon, and Meta.

What data structure is used in Fixed Point?

The problem operates on a sorted array. The key technique is binary search, which relies on the ordered structure of the array and the monotonic property of the expression nums[i] - i.

What is the time complexity of Fixed Point?

The brute force linear scan runs in O(n) time and O(1) space because it checks every index. The optimized binary search solution runs in O(log n) time with O(1) space by repeatedly halving the search range using comparisons between nums[mid] and mid.

1064. Fixed Point - Practice Online

Given an array of distinct integers arr, where arr is sorted in ascending order, return the smallest index i that satisfies arr[i] == i. If there is no such index, return -1.

Example 1:

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

Example 2:

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

Example 3:

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

Constraints:

1 <= arr.length < 10⁴
-10⁹ <= arr[i] <= 10⁹

Follow up: The O(n) solution is very straightforward. Can we do better?