Domain 1EasyCORE

Fixed Point

The problem asks us to find the smallest index `i` in a sorted array of distinct integers where the value at that index equals the index itself (`arr[i] == i`). If no such index exists, we should return `-1`. The input is an array of integers, and the output is an integer representing the index. The constraints are that the array length is between 1 and 10,000, and each element can range from -1 billion to 1 billion.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Array#Binary Search

1064. Fixed Point

Model: qwen2.5-coder:14b
Topics: Array,Binary Search
FAANG asked: 0
Acceptance rate: 64.8%


Problem Breakdown

The problem asks us to find the smallest index i in a sorted array of distinct integers where the value at that index equals the index itself (arr[i] == i). If no such index exists, we should return -1. The input is an array of integers, and the output is an integer representing the index. The constraints are that the array length is between 1 and 10,000, and each element can range from -1 billion to 1 billion.

Intuition

A brute-force approach would involve iterating through the array and checking if arr[i] == i for each index i. This solution has a time complexity of O(n), which is acceptable but not optimal given that the array is sorted. The key insight is to leverage binary search, as it can reduce the time complexity to O(log n). Since the array is sorted and contains distinct integers, we can use binary search to efficiently find the fixed point.

Approach

  1. Initialize Pointers: Start with two pointers, left at the beginning of the array (index 0) and right at the end of the array (index len(arr) - 1).
  2. Binary Search Loop: While left is less than or equal to right, calculate the middle index mid.
  3. Check Middle Element:
    • If arr[mid] == mid, we have found a fixed point. However, since we need the smallest index, continue searching in the left half by setting right = mid - 1.
    • If arr[mid] < mid, move the left pointer to mid + 1 because any potential fixed point must be in the right half.
    • If arr[mid] > mid, move the right pointer to mid - 1 because any potential fixed point must be in the left half.
  4. Return Result: After exiting the loop, if a fixed point was found, return the smallest index stored during the search. Otherwise, return -1.

Complexity Analysis

  • Time Complexity: O(log n) due to the binary search approach.
  • Space Complexity: O(1) as we are using only a constant amount of extra space for pointers.

Solution

def fixedPoint(arr):
    left, right = 0, len(arr) - 1
    smallest_index = float('inf')
    
    while left <= right:
        mid = (left + right) // 2
        
        if arr[mid] == mid:
            smallest_index = min(smallest_index, mid)
            right = mid - 1  # Continue searching in the left half
        elif arr[mid] < mid:
            left = mid + 1
        else:
            right = mid - 1
    
    return smallest_index if smallest_index != float('inf') else -1

Edge Cases Handled

  • No Fixed Point: If no index satisfies arr[i] == i, the function returns -1.
  • Single Element Array: The function correctly handles arrays with a single element.
  • All Negative Numbers: The function works correctly even if all numbers in the array are negative.
  • All Positive Numbers: The function also works correctly for arrays with all positive numbers.