LeetCode 1064 - Fixed Point

LeetCode Problem 1064

Difficulty: 🟢 Easy
Topics: Array, Binary Search

Solution

Problem Understanding

The problem is asking us to find a "fixed point" in a sorted array of distinct integers. A fixed point is an index i such that the value at that index equals the index itself, i.e., arr[i] == i. The input is an array arr of integers sorted in ascending order, and we need to return the smallest index where this property holds. If no such index exists, we return -1.

The constraints tell us that the array length can be up to 10,000 elements and each element can range from -10^9 to 10^9. Because the array is sorted and values are distinct, we can leverage this property to optimize our solution rather than scanning linearly.

Important edge cases include arrays where the fixed point occurs at the beginning (arr[0] == 0) or at the end (arr[n-1] == n-1), arrays where all elements are negative or positive (no fixed point exists), and arrays of length 1.

Approaches

The brute-force approach is straightforward: iterate through the array from start to end and check each index i to see if arr[i] == i. This works correctly because it directly checks the condition for every element, but it runs in O(n) time, which is acceptable for small arrays but can be improved for larger arrays using the sorted property.

The optimal approach uses binary search. Since the array is sorted and elements are distinct, if arr[mid] < mid, all fixed points must be to the right, and if arr[mid] > mid, all fixed points must be to the left. This is because a smaller value than the index means we need larger values (to potentially match the index), and a larger value than the index means earlier indices might match. By using binary search, we can reduce the time complexity to O(log n).

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(1)	Iterate through the array checking each index
Optimal	O(log n)	O(1)	Use binary search leveraging the sorted distinct property

Algorithm Walkthrough

1. Initialize two pointers, left = 0 and right = len(arr) - 1. These represent the search space of indices.
2. While left <= right, compute the middle index mid = (left + right) // 2.
3. Compare arr[mid] with mid.

• If arr[mid] == mid, we have found a fixed point, but we continue searching to the left to find the smallest index, so set right = mid - 1.
• If arr[mid] < mid, the fixed point, if it exists, must be to the right of mid, so set left = mid + 1.
• If arr[mid] > mid, the fixed point, if it exists, must be to the left of mid, so set right = mid - 1.

4. Keep track of the smallest fixed point found during the search.
5. If no fixed point was found after the search, return -1. Otherwise, return the smallest index recorded.

Why it works: The binary search maintains the invariant that any fixed point must lie within the search bounds. By always halving the search space based on the comparison of arr[mid] and mid, we guarantee we will find the smallest fixed point efficiently.

Python Solution

from typing import List

class Solution:
    def fixedPoint(self, arr: List[int]) -> int:
        left, right = 0, len(arr) - 1
        result = -1
        
        while left <= right:
            mid = (left + right) // 2
            if arr[mid] == mid:
                result = mid
                right = mid - 1  # search left side for smaller index
            elif arr[mid] < mid:
                left = mid + 1
            else:
                right = mid - 1
        
        return result

This implementation uses a binary search approach. We maintain two pointers to search efficiently and a result variable to store the smallest fixed point found. By adjusting left and right based on the comparison, we ensure we do not miss any potential smaller fixed point to the left of mid.

Go Solution

func fixedPoint(arr []int) int {
    left, right := 0, len(arr)-1
    result := -1
    
    for left <= right {
        mid := (left + right) / 2
        if arr[mid] == mid {
            result = mid
            right = mid - 1
        } else if arr[mid] < mid {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    
    return result
}

The Go implementation mirrors the Python version. The main differences are the use of := for variable declaration and the absence of a List[int] type. Empty arrays are naturally handled, and integer overflow is not an issue with the mid calculation in Go since the constraints are within 32-bit int range.

Worked Examples

Example 1: arr = [-10,-5,0,3,7]

left	right	mid	arr[mid]	action	result
0	4	2	0	arr[mid] < mid → left=3	-1
3	4	3	3	arr[mid] == mid → result=3, right=2	3

Return 3.

Example 2: arr = [0,2,5,8,17]

left	right	mid	arr[mid]	action	result
0	4	2	5	arr[mid] > mid → right=1	-1
0	1	0	0	arr[mid] == mid → result=0, right=-1	0

Return 0.

Example 3: arr = [-10,-5,3,4,7,9]

left	right	mid	arr[mid]	action	result
0	5	2	3	arr[mid] > mid → right=1	-1
0	1	0	-10	arr[mid] < mid → left=1	-1
1	1	1	-5	arr[mid] < mid → left=2	-1

Return -1.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(log n)	Binary search halves the search space each iteration, giving logarithmic time
Space	O(1)	No extra space used beyond a few variables

The binary search is efficient because the array is sorted and contains distinct integers, allowing us to eliminate half of the array in each step without missing any potential fixed points.

Test Cases

# Provided examples
assert Solution().fixedPoint([-10,-5,0,3,7]) == 3  # middle fixed point
assert Solution().fixedPoint([0,2,5,8,17]) == 0   # first element is fixed point
assert Solution().fixedPoint([-10,-5,3,4,7,9]) == -1  # no fixed point

# Edge cases
assert Solution().fixedPoint([-1,0,1,3,5]) == 3   # fixed point not at start or end
assert Solution().fixedPoint([0]) == 0           # single element fixed point
assert Solution().fixedPoint([1]) == -1          # single element no fixed point
assert Solution().fixedPoint([-5,-4,-3,-2,-1]) == -1  # all negative numbers
assert Solution().fixedPoint([0,1,2,3,4]) == 0        # first fixed point

Test	Why
[-10,-5,0,3,7]	Validates normal case with middle fixed point
[0,2,5,8,17]	Checks first element fixed point
[-10,-5,3,4,7,9]	Ensures no fixed point returns -1
[-1,0,1,3,5]	Tests array with fixed point not at edges
[0]	Single element fixed point
[1]	Single element no fixed point
[-5,-4,-3,-2,-1]	All negative numbers, no fixed point
[0,1,2,3,4]	Multiple fixed points, return smallest index

Edge Cases

1. Array of length 1: If the array has only one element, it may or may not be a fixed point. A naive loop would still work, but binary search handles it naturally by evaluating mid = 0 and returning accordingly.