LeetCode 1533 - Find the Index of the Large Integer
The problem presents an array arr where all elements are equal except for one element that is strictly larger than the o
Difficulty: 🟡 Medium
Topics: Array, Binary Search, Interactive
Solution
Problem Understanding
The problem presents an array arr where all elements are equal except for one element that is strictly larger than the others. However, we do not have direct access to the array elements. Instead, we interact with the array through an API called ArrayReader. This API provides two functions: compareSub(l, r, x, y), which allows us to compare the sums of two subarrays, and length(), which returns the size of the array.
The goal is to identify the index of the single largest element using at most 20 calls to compareSub(). The problem guarantees that exactly one element is larger, which ensures that a search strategy can uniquely identify the correct index. The array can have up to 500,000 elements, so any solution that examines elements sequentially would be too slow or exceed the allowed number of comparisons.
Key edge cases include very small arrays (length 2 or 3), cases where the largest element is at the beginning or end of the array, and situations where repeated subarray comparisons are necessary to narrow down the search space efficiently.
Approaches
The brute-force approach would involve comparing each element individually with the others using compareSub. While this guarantees finding the largest element, it could require up to n-1 comparisons, which is not feasible for large arrays and violates the 20-call limit. For instance, with arr.length = 500,000, we would need potentially 499,999 calls.
The optimal approach relies on a binary search-inspired technique using compareSub to split the array into halves. The key insight is that we can compare the sums of the left and right halves of any segment. If the sums are equal, the larger element is not in either half, but since there is exactly one larger element, the unequal sum half must contain it. We then recursively narrow the search space until only one element remains, which must be the largest. This approach ensures at most O(log n) calls, well within the 20-call limit.
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(n) | O(1) | Compare each element individually; exceeds API call limit for large arrays |
| Optimal | O(log n) | O(1) | Binary search using compareSub; guarantees ≤ 20 calls for n <= 5 * 10^5 |
Algorithm Walkthrough
- Start with the full range of the array,
[0, n-1], wheren = reader.length(). - While the range has more than one element, split it into two nearly equal halves.
- If the length of the segment is even, compare the left half with the right half using
compareSub. If the sum of the left half is larger, the larger element lies in the left half. If the sum of the right half is larger, it lies in the right half. - If the length is odd, exclude the middle element and compare the sums of the remaining halves. If the sums are equal, the middle element is the largest. Otherwise, focus on the half with the larger sum.
- Repeat this process until only one index remains. Return that index as the position of the largest element.
Why it works: At each step, the algorithm maintains the invariant that the largest element is always within the current search range. By halving the search space at every step, we guarantee logarithmic convergence to the single largest element. This ensures correctness while staying within the API call limit.
Python Solution
class Solution:
def getIndex(self, reader: 'ArrayReader') -> int:
left, right = 0, reader.length() - 1
while left < right:
n = right - left + 1
if n % 2 == 0:
mid = left + n // 2 - 1
cmp = reader.compareSub(left, mid, mid + 1, right)
if cmp == 1:
right = mid
else:
left = mid + 1
else:
mid = left + n // 2
cmp = reader.compareSub(left, mid - 1, mid + 1, right)
if cmp == 0:
return mid
elif cmp == 1:
right = mid - 1
else:
left = mid + 1
return left
The code initializes two pointers representing the current search range. It repeatedly splits the range and uses compareSub to determine which half contains the larger element. Odd-length segments are handled by checking the middle element directly if needed. The loop continues until a single index remains, which is returned as the answer.
Go Solution
func getIndex(reader *ArrayReader) int {
left, right := 0, reader.length()-1
for left < right {
n := right - left + 1
if n%2 == 0 {
mid := left + n/2 - 1
cmp := reader.compareSub(left, mid, mid+1, right)
if cmp == 1 {
right = mid
} else {
left = mid + 1
}
} else {
mid := left + n/2
cmp := reader.compareSub(left, mid-1, mid+1, right)
if cmp == 0 {
return mid
} else if cmp == 1 {
right = mid - 1
} else {
left = mid + 1
}
}
}
return left
}
In Go, we follow the same logic as the Python version. Go requires handling integer division carefully and the loop variables are explicitly declared. Nil handling is not necessary since reader is guaranteed to exist, and array overflow is not a concern due to the constraints.
Worked Examples
Example 1: arr = [7,7,7,7,10,7,7,7]
| Iteration | left | right | n | mid | compareSub(left..mid, mid+1..right) | Result |
|---|---|---|---|---|---|---|
| 1 | 0 | 7 | 8 | 3 | compareSub(0,3,4,7) = -1 | left = 4 |
| 2 | 4 | 7 | 4 | 5 | compareSub(4,5,6,7) = 1 | right = 5 |
| 3 | 4 | 5 | 2 | 4 | compareSub(4,4,5,5) = 1 | right = 4 |
| Done | 4 | 4 | 1 | - | - | return 4 |
Example 2: arr = [6,6,12]
| Iteration | left | right | n | mid | compareSub(left..mid-1, mid+1..right) | Result |
|---|---|---|---|---|---|---|
| 1 | 0 | 2 | 3 | 1 | compareSub(0,0,2,2) = -1 | left = 2 |
| Done | 2 | 2 | 1 | - | - | return 2 |
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(log n) | Each compareSub call halves the search space, so logarithmic calls suffice |
| Space | O(1) | Only pointers are used; no additional data structures needed |
This is efficient for the maximum array length of 500,000 while staying well within the 20-call limit.
Test Cases
# Provided examples
assert Solution().getIndex(reader_mock([7,7,7,7,10,7,7,7])) == 4 # largest element in middle
assert Solution().getIndex(reader_mock([6,6,12])) == 2 # largest element at end
# Edge cases
assert Solution().getIndex(reader_mock([10,20])) == 1 # smallest array
assert Solution().getIndex(reader_mock([20,10])) == 0 # largest at beginning
assert Solution().getIndex(reader_mock([7]*499999 + [8])) == 499999 # large array, largest at end
assert Solution().getIndex(reader_mock([8] + [7]*499999)) == 0 # large array, largest at start
| Test | Why |
|---|---|
| [7,7,7,7,10,7,7,7] | Middle element is largest |
| [6,6,12] | Largest element at the end |
| [10,20] | Minimum size array |
| [20,10] | Largest element at start |
| [7]*499999 + [8] | Stress test, largest at end |
| [8] + [7]*499999 | Stress test, largest at start |
Edge Cases
- Two-element arrays: The algorithm must handle arrays of length 2 correctly, comparing the two elements directly. The implementation correctly checks
compareSubbetween the two elements and returns the larger. - Odd-length arrays: Odd-length arrays require careful handling of the middle element. If the sums of the left and right halves are