1064. Fixed Point

EasyArrayBinary Search
Leetcode Link

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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which of the following array represent a max heap?

Solution Approach

The implementation of the solution uses a binary search algorithm. Here's how it is applied to the given problem:

  1. We initialize two pointers, left and right, which represent the bounds of the search range. Initially, left is set to 0 (the first index of the array) and right is set to len(arr) - 1 (the last index of the array).

  2. We enter a while loop, which runs as long as left < right. Inside the loop, we find the midpoint mid by averaging the current left and right indices (using bit shifting >> for efficiency, which is the same as dividing by 2).

  3. At each step, we compare the value at the midpoint arr[mid] with the mid itself to determine where to continue our search:

    • If arr[mid] >= mid, then we move the right pointer to mid because the fixed point could be at this position or to the left of it.
    • If arr[mid] < mid, then we move the left pointer to mid + 1 because a fixed point cannot exist to the left of mid, given the properties of the sorted array.

  4. The loop ends when left and right converge, meaning the search space has been narrowed down to a single element. At this point, we have potentially found the smallest index i where arr[i] == i.

  5. Finally, we perform a check by comparing the element at the left index with left itself. If they are equal, we have found the fixed point and return left. If they are not, it means there are no elements where arr[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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which data structure is used to implement priority queue?

Example 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.

  1. We initialize two pointers: left is 0 and right is 4 (since the length of arr is 5, right is len(arr) - 1).

  2. Our first while loop iteration starts:

    • Calculate mid: (left + right) / 2, which is (0 + 4) / 2. So, mid is 2.
    • The value at index 2 is 0. Since arr[mid] == mid (0 == 2 is false), we check if arr[mid] < mid.
    • Since 0 (the value at mid) is less than 2 (mid), we set left to mid + 1, which is 3.

  3. Our next iteration begins with left as 3 and right as 4:

    • Calculate the new mid: (left + right) / 2, which is (3 + 4) / 2. So, mid is 3.
    • The value at index 3 is 3. Check if arr[mid] == mid. Since 3 == 3 is true, we have found our fixed point.

  4. Since we have found the index where arr[i] == i, we return the value of left, which is 3.

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
Not Sure What to Study? Take the 2-min Quiz：

Consider the classic dynamic programming of longest increasing subsequence:

Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

For example, the length of LIS for [50, 3, 10, 7, 40, 80] is 4 and LIS is [3, 7, 40, 80].

What is the recurrence relation?

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.

Fast Track Your Learning with Our Quick Skills Quiz:

Which algorithm is best for finding the shortest distance between two points in an unweighted graph?

Recommended Readings

Binary Search Speedrun

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 - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

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 Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫