Skip to main content
Talentd

Fixed Point - Solution & Explanation

EasyPremiumFree on FleetCodeArrayBinary Search4 min readAsked at: Uber
Practice this problem

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 such i that arr[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.

Solution

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Linear ScanO(n)O(1)Simple baseline solution or when array size is small
Binary Search on nums[i] - iO(log n)O(1)When the array is sorted with distinct integers and optimal performance is required

Video Solution

Leetcode 1064 - Fixed Point • Shafik Quoraishee • 228 views views

Watch 6 more video solutions →

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.

Ready to solve this problem?

Practice Fixed Point with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays