Problem Description

The Fixed Point problem on Leetcode asks you to find an index i in a sorted array of distinct integers arr such that arr[i] == i. If such an index exists, return it. If there are multiple possible indices, return any one of them. If no such index exists, return -1.

• The input arr is a sorted array of distinct integers (may include negative numbers).
• Constraints: The array can be of any length, and there may be zero or more fixed points, but you only need to return one if it exists.
• Only one index is to be returned, and the elements cannot be reused (since you are looking for arr[i] == i at a single index).

Thought Process

The simplest way to solve this problem is to check every index i and see if arr[i] == i. This is a brute-force approach and works, but it can be slow if the array is large.

However, because the array is sorted and has distinct elements, we can do better. If we think about how the values in the array relate to their indices, we can use a binary search approach, similar to searching for a target value in a sorted array.

The key insight is that if arr[mid] < mid, then all values to the left of mid will also be less than their indices (because the array is sorted and strictly increasing). Similarly, if arr[mid] > mid, all values to the right will be greater than their indices. This allows us to eliminate half the search space at each step.

Solution Approach

We'll use a binary search algorithm to efficiently find a fixed point. Here is how we break down the solution:

1. Initialize two pointers, left and right, at the start and end of the array.
2. While left <= right:
   • Find the mid index: mid = (left + right) // 2.
   • If arr[mid] == mid, we've found a fixed point and return mid.
   • If arr[mid] < mid, move the left pointer to mid + 1 (search right half).
   • If arr[mid] > mid, move the right pointer to mid - 1 (search left half).
3. If no fixed point is found after the loop, return -1.

This approach is much faster than brute-force because it halves the search space at each step, leveraging the sorted, distinct property of the array.

Example Walkthrough

Let's walk through an example with arr = [-10, -5, 0, 3, 7]:

1. Start: left = 0, right = 4
2. mid = (0 + 4) // 2 = 2. arr[2] = 0, but 0 != 2.
3. Since arr[2] < 2, search right half: left = 3, right = 4
4. mid = (3 + 4) // 2 = 3. arr[3] = 3, and 3 == 3.
5. We've found a fixed point at index 3.

The algorithm stops as soon as it finds a fixed point.

Time and Space Complexity

Brute-force approach:

• Time Complexity: O(n), since we check every index.
• Space Complexity: O(1), as we use no extra space.

• Time Complexity: O(log n), because we halve the search space at each step.
• Space Complexity: O(1), as we only use a few pointers.

The optimized approach is much faster for large arrays due to the logarithmic time complexity.

Summary

The Fixed Point problem leverages the sorted and distinct nature of the input array to efficiently locate an index where arr[i] == i. By applying a binary search instead of a brute-force scan, we reduce time complexity from linear to logarithmic. The main insight is recognizing how the relationship between arr[mid] and mid allows us to eliminate half the possibilities at each step, making the solution both elegant and efficient.

Code Implementation

class Solution:
    def fixedPoint(self, arr):
        left, right = 0, len(arr) - 1
        while left <= right:
            mid = (left + right) // 2
            if arr[mid] == mid:
                return mid
            elif arr[mid] < mid:
                left = mid + 1
            else:
                right = mid - 1
        return -1
      

class Solution {
public:
    int fixedPoint(vector<int>& arr) {
        int left = 0, right = arr.size() - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] == mid) {
                return mid;
            } else if (arr[mid] < mid) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1;
    }
};
      

class Solution {
    public int fixedPoint(int[] arr) {
        int left = 0, right = arr.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] == mid) {
                return mid;
            } else if (arr[mid] < mid) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1;
    }
}
      

var fixedPoint = function(arr) {
    let left = 0, right = arr.length - 1;
    while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        if (arr[mid] === mid) {
            return mid;
        } else if (arr[mid] < mid) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;
};