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
- Initialize Pointers: Start with two pointers,
leftat the beginning of the array (index 0) andrightat the end of the array (indexlen(arr) - 1). - Binary Search Loop: While
leftis less than or equal toright, calculate the middle indexmid. - 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 settingright = mid - 1. - If
arr[mid] < mid, move theleftpointer tomid + 1because any potential fixed point must be in the right half. - If
arr[mid] > mid, move therightpointer tomid - 1because any potential fixed point must be in the left half.
- If
- 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.