We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Fixed Point

Number: 1066

Difficulty: Easy

Paid? Yes

Companies: Uber

Problem Description

Given a sorted array of distinct integers, find the smallest index i such that arr[i] == i. If no such index exists, return -1. An O(n) solution is straightforward, but the goal is to achieve better than linear time.

Key Insights

  • The array is sorted and contains distinct integers.
  • A fixed point is an index i where arr[i] equals i.
  • The function f(i) = arr[i] - i is strictly increasing; this enables the use of a binary search.
  • Use binary search to efficiently locate the fixed point in O(log n) time.

Space and Time Complexity

Time Complexity: O(log n)
Space Complexity: O(1)

Solution

The solution uses a binary search approach. We initialize two pointers, low and high, and compute the mid index. At each step, if arr[mid] equals mid, we found a fixed point and then search to the left to check if a smaller fixed point exists. If arr[mid] is less than mid, we discard the left portion by setting low to mid + 1. If arr[mid] is greater than mid, we discard the right portion by setting high to mid - 1. This leverages the strictly increasing property of arr[i] - i, ensuring an efficient search for the smallest fixed point.

Code Solutions

def fixed_point(arr):
    # Initialize low and high pointers for binary search.
    low, high = 0, len(arr) - 1
    result = -1  # Default result if no fixed point is found.
    while low <= high:
        mid = low + (high - low) // 2  # Calculate the mid index.
        if arr[mid] == mid:
            result = mid  # Fixed point found; record result.
            high = mid - 1  # Search left subarray for a smaller fixed point.
        elif arr[mid] < mid:
            low = mid + 1  # Discard left subarray.
        else:
            high = mid - 1  # Discard right subarray.
    return result

# Example usage:
print(fixed_point([-10, -5, 0, 3, 7]))   # Output: 3
print(fixed_point([0, 2, 5, 8, 17]))       # Output: 0
print(fixed_point([-10, -5, 3, 4, 7, 9]))   # Output: -1
← Back to All Questions