Leetcode 1064 - Fixed Point
Fixed Point - Video Solution
Watch 7 video solutions for Fixed Point, a easy level problem involving Array, Binary Search. This walkthrough by Shafik Quoraishee has 228 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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
Follow up: The
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.
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 |