1064. Fixed Point
Problem Description
In this problem, we are given a sorted array of distinct integers, arr
. The array is sorted in ascending order. The task is to find the smallest index i
such that the element at that index is equal to its index value, i.e., arr[i] == i
. If no such index exists, the function should return -1
. This problem is essentially asking us to find the point, if any, where the value of the array matches its index.
Intuition
The intuitive approach to this problem relies on the properties of the sorted array. To find the smallest index where the value equals the index, we don't have to look at each element of the array; instead, we can use binary search because of the array's sorted nature. Binary search works by repeatedly dividing the search interval in half, eliminating half of the remaining elements at each step.
If the value at the middle index is less than the middle index itself, then we know that the fixed point, if it exists, must be on the right side of the middle index. This is because the values are distinct and increasing, and if arr[mid] < mid
, then all values left of mid
must also be less than their indices, so we can ignore the left side.
Conversely, if the value at the middle index is greater than or equal to the middle index, the fixed point might be at this position or to the left. In this case, we set the new right bound to be the current middle index.
After iteratively applying binary search and narrowing down the search space, if we find an index where arr[i] == i
, we return it. If we exhaust the search space without finding such an index, we return -1
because no element satisfies the condition.
Learn more about Binary Search patterns.
Solution Approach
The implementation of the solution uses a binary search algorithm. Here's how it is applied to the given problem:
-
We initialize two pointers,
left
andright
, which represent the bounds of the search range. Initially,left
is set to0
(the first index of the array) andright
is set tolen(arr) - 1
(the last index of the array). -
We enter a while loop, which runs as long as
left < right
. Inside the loop, we find the midpointmid
by averaging the currentleft
andright
indices (using bit shifting>>
for efficiency, which is the same as dividing by 2). -
At each step, we compare the value at the midpoint
arr[mid]
with themid
itself to determine where to continue our search:- If
arr[mid] >= mid
, then we move theright
pointer tomid
because the fixed point could be at this position or to the left of it. - If
arr[mid] < mid
, then we move theleft
pointer tomid + 1
because a fixed point cannot exist to the left ofmid
, given the properties of the sorted array.
- If
-
The loop ends when
left
andright
converge, meaning the search space has been narrowed down to a single element. At this point, we have potentially found the smallest indexi
wherearr[i] == i
. -
Finally, we perform a check by comparing the element at the
left
index withleft
itself. If they are equal, we have found the fixed point and returnleft
. If they are not, it means there are no elements wherearr[i] == i
, so we return-1
.
The code does not require any additional data structures, as it only uses the input array arr
and manipulates the left
and right
pointers to perform the binary search.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's go through a small example to illustrate the solution approach.
Suppose the input array arr
is [-10, -5, 0, 3, 7]
. We need to find the smallest index i
such that arr[i] == i
.
-
We initialize two pointers:
left
is0
andright
is4
(since the length ofarr
is5
,right
islen(arr) - 1
). -
Our first while loop iteration starts:
- Calculate
mid
:(left + right) / 2
, which is(0 + 4) / 2
. So,mid
is2
. - The value at index
2
is0
. Sincearr[mid] == mid
(0 == 2
is false), we check ifarr[mid] < mid
. - Since
0
(the value atmid
) is less than2
(mid
), we setleft
tomid + 1
, which is3
.
- Calculate
-
Our next iteration begins with
left
as3
andright
as4
:- Calculate the new
mid
:(left + right) / 2
, which is(3 + 4) / 2
. So,mid
is3
. - The value at index
3
is3
. Check ifarr[mid] == mid
. Since3 == 3
is true, we have found our fixed point.
- Calculate the new
-
Since we have found the index where
arr[i] == i
, we return the value ofleft
, which is3
.
To summarize, in our example array [-10, -5, 0, 3, 7]
, the smallest index at which the value of the array matches its index is 3
, because arr[3] == 3
.
Solution Implementation
1from typing import List
2
3class Solution:
4 def fixedPoint(self, arr: List[int]) -> int:
5 # Initialize the left and right pointers
6 left, right = 0, len(arr) - 1
7
8 # Use a binary search approach to find the fixed point
9 while left < right:
10 # Find the middle index using bitwise right shift
11 # which is equivalent to dividing by 2.
12 mid = (left + right) // 2
13
14 # If the middle element is greater than or equal to its index,
15 # the fixed point must be to the left, including mid.
16 if arr[mid] >= mid:
17 right = mid
18 else:
19 # If the middle element is less than its index,
20 # the fixed point must be to the right, so we
21 # exclude the middle element by incrementing left.
22 left = mid + 1
23
24 # After the loop, if the element at the left index is equal
25 # to the index itself, then we've found the fixed point.
26 # Otherwise, return -1 as the fixed point does not exist.
27 return left if arr[left] == left else -1
28
1class Solution {
2
3 /**
4 * Finds a fixed point in the array where arr[i] == i.
5 * If no such point exists, returns -1.
6 *
7 * @param arr The input array to be searched for a fixed point.
8 * @return The index of the fixed point or -1 if none exists.
9 */
10 public int fixedPoint(int[] arr) {
11 int left = 0;
12 int right = arr.length - 1;
13
14 // Use binary search to find the fixed point
15 while (left < right) {
16 // Calculate mid index
17 int mid = left + (right - left) / 2; // Avoids potential overflow compared to (left + right) >> 1
18
19 // Check if the mid index is a fixed point
20 if (arr[mid] >= mid) {
21 right = mid; // The fixed point is at mid or to the left of mid
22 } else {
23 left = mid + 1; // The fixed point can only be to the right of mid
24 }
25 }
26
27 // After the loop, left should point to the smallest candidate for fixed point
28 // Check if the final left index is indeed a fixed point
29 return arr[left] == left ? left : -1;
30 }
31}
32
1class Solution {
2public:
3 int fixedPoint(vector<int>& arr) {
4 // Initialize the search space boundaries.
5 int left = 0;
6 int right = arr.size() - 1;
7
8 // Use binary search within the loop.
9 while (left < right) {
10 // Compute the middle index avoiding potential overflow.
11 int mid = left + (right - left) / 2;
12
13 // If the value at the mid index is greater than or equal to mid,
14 // we need to search on the left side including mid, as the fixed point
15 // could be at mid or to its left.
16 if (arr[mid] >= mid) {
17 right = mid;
18 } else {
19 // The value at mid is less than mid, so the fixed point
20 // must be on the right side, excluding mid.
21 left = mid + 1;
22 }
23 }
24
25 // At the end of the loop, left is the smallest index where arr[left] >= left.
26 // If arr[left] == left, we have found the fixed point; otherwise, return -1.
27 return arr[left] == left ? left : -1;
28 }
29};
30
1function fixedPoint(numbers: number[]): number {
2 // Initialize pointers for the start and end of the array
3 let start = 0;
4 let end = numbers.length - 1;
5
6 // Use binary search to find the fixed point
7 while (start < end) {
8 // Calculate the middle index
9 const middle = (start + end) >> 1; // same as Math.floor((start + end) / 2)
10
11 // If the element at the middle index is greater than or equal to the index,
12 // the fixed point must be to the left, including the middle
13 if (numbers[middle] >= middle) {
14 end = middle;
15 } else {
16 // If the element at the middle index is less than the index,
17 // the fixed point must be to the right
18 start = middle + 1;
19 }
20 }
21
22 // After the loop, start is the potential fixed point.
23 // Check if the value at this index equals the index itself
24 return numbers[start] === start ? start : -1;
25}
26
Time and Space Complexity
Time Complexity
The provided code uses a binary search algorithm to find a fixed point in the array. Binary search repeatedly divides the array into half to look for the fixed point, resulting in a logarithmic time complexity. Since it narrows down the search space by half at each step and performs a constant number of operations at each level, the time complexity is O(log n)
, where n
is the length of the array.
Space Complexity
The space complexity of the algorithm is O(1)
. The solution is an in-place algorithm, meaning it requires a constant amount of additional space regardless of the input size. The variables left
, right
, mid
, and the space for the return value do not scale with the size of the input array.
Learn more about how to find time and space complexity quickly using problem constraints.
Which two pointer techniques do you use to check if a string is a palindrome?
Recommended Readings
Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.