Fixed Point solution and explanation
6 more videos on this problem
Leetcode 1064 - Fixed PointShafik Quoraishee · 9:19 · 228 views
猩猩的乐园 Leetcode 1064 Fixed Point猩猩的乐园 · 2:31 · 125 views
LeetCode 1064 | Fixed Point | Array | JavaSleepy Cracker · 1:37 · 50 views
Leetcode 1064. Fixed Point (binary search)LetsCode · 5:16 · 37 views
Java Leet code 1064. Fixed PointJava Programming · 5:25 · 5 views
LeetCode 1064: Fixed PointAlitaCode · 29:05 · 5 views
LeetCode 1064: Fixed Point — The Binary Search Trick (C#)DSA Mastery Lab · 3:44 · 3 views
The problem
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 suchithatarr[i] == i, thus the output is -1.
Constraints:
1 <= arr.length < 104-109 <= arr[i] <= 109
O(n) solution is very straightforward. Can we do better?Approach overview
Problem Overview: Given a sorted array of distinct integers, return the smallest index i such that nums[i] == i. This index is called a fixed point. If no such index exists, return -1. The sorted property of the array is the key constraint that allows faster solutions.
Approach 1: Linear Scan (O(n) time, O(1) space)
The simplest method is to iterate through the array and check each position. For every index i, compare nums[i] with i. If they match, return the index immediately. If the loop finishes without finding a match, return -1. This approach uses basic array traversal and works for any input but does not take advantage of the sorted property.
Approach 2: Binary Search on Value-Index Difference (O(log n) time, O(1) space)
Because the array is sorted and contains distinct values, the function f(i) = nums[i] - i is strictly increasing. If nums[mid] < mid, then f(mid) is negative, meaning all indices on the left will also have nums[i] - i < 0. The fixed point cannot exist there, so move the search to the right half. If nums[mid] > mid, the value is too large and the fixed point must be on the left side. When nums[mid] == mid, record it and continue searching the left half to ensure it is the smallest index. This classic binary search pattern reduces the search space by half each step.
The algorithm initializes left = 0 and right = n - 1. While left <= right, compute mid. Compare nums[mid] with mid and adjust the boundaries accordingly. Tracking the candidate index ensures you return the smallest valid fixed point.
Recommended for interviews: Start by mentioning the linear scan to show the baseline O(n) idea. Then explain why the sorted array allows a faster solution. Interviewers typically expect the binary search approach with O(log n) time and constant space. Recognizing the monotonic behavior of nums[i] - i demonstrates strong algorithmic reasoning.
Solution
class Solution:
def fixedPoint(self, arr: List[int]) -> int:
left, right = 0, len(arr) - 1
while left < right:
mid = (left + right) >> 1
if arr[mid] >= mid:
right = mid
else:
left = mid + 1
return left if arr[left] == left else -1class Solution {
public int fixedPoint(int[] arr) {
int left = 0, right = arr.length - 1;
while (left < right) {
int mid = (left + right) >> 1;
if (arr[mid] >= mid) {
right = mid;
} else {
left = mid + 1;
}
}
return arr[left] == left ? left : -1;
}
}class Solution {
public:
int fixedPoint(vector<int>& arr) {
int left = 0, right = arr.size() - 1;
while (left < right) {
int mid = left + right >> 1;
if (arr[mid] >= mid) {
right = mid;
} else {
left = mid + 1;
}
}
return arr[left] == left ? left : -1;
}
};function fixedPoint(arr: number[]): number {
let left = 0;
let right = arr.length - 1;
while (left < right) {
const mid = (left + right) >> 1;
if (arr[mid] >= mid) {
right = mid;
} else {
left = mid + 1;
}
}
return arr[left] === left ? left : -1;
}func fixedPoint(arr []int) int {
left, right := 0, len(arr)-1
for left < right {
mid := (left + right) >> 1
if arr[mid] >= mid {
right = mid
} else {
left = mid + 1
}
}
if arr[left] == left {
return left
}
return -1
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Linear Scan | O(n) | O(1) | Simple baseline solution or when array size is small |
| Binary Search on nums[i] - i | O(log n) | O(1) | When the array is sorted with distinct integers and optimal performance is required |
Frequently asked questions
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, move to the right half; 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.