1533. Find the Index of the Large Integer

Problem Description

In this problem, we are given a unique integer array where all elements are equal except for one that is larger than the others. Instead of direct access to the array, we are provided an API ArrayReader with two functions: compareSub and length. Our objective is to find the index of the element that is larger than the rest using the ArrayReader API, with the constraint of calling compareSub a maximum of 20 times.

The compareSub function compares the sum of two sub-arrays within given indices and returns 1 if the first is larger, -1 if the second is larger, and 0 if they are equal. length returns the size of the array. It's important to note that both API functions are considered to operate in constant time, O(1).

Intuition

Given that all elements of the array are equal except for one, we can use a divide and conquer strategy to narrow down the search space efficiently. To do this, we can partition the array into three equal parts and use the compareSub method to compare the sums of these parts.

The intuition is that the unique element, which is larger, will cause the sum of the part containing it to be greater than the others. Based on the comparison results, we can eliminate two-thirds of the array in each step, as follows:

If the sum of the first and the second third is the same (compareSub returns 0), the element must be in the last third.
If the sum of the first third is greater than the sum of the second (compareSub returns 1), the element must be in the first third.
If the sum of the second third is greater than the sum of the first (compareSub returns -1), the element must be in the second third.

By repeating this process and shrinking the search interval, we eventually isolate the unique element's index. Our approach guarantees that we will find the index with a minimal number of calls to the compareSub function, well within the 20 call limit.

Learn more about Binary Search patterns.

Solution Approach

The implementation of the solution follows a ternary search approach to identify the segment containing the unique element that is larger than the others.

The algorithm initializes two pointers, left and right, representing the search boundaries, which at the beginning correspond to the start and end indices of the array, respectively.

In each iteration of the while loop, which continues as long as left is less than right, the search space is divided into thirds by calculating two indices, t2 and t3:

t1 is set to left, the beginning of the current search space.
t2 is calculated as left + (right - left) // 3, which is one-third into the current search space.
t3 is left + 2 * ((right - left) // 3) + 1, which is two-thirds into the current search space.

The solution then uses these indices to call compareSub(t1, t2, t2 + 1, t3). This comparison effectively evaluates the sum of the first third against the sum of the second third of the search space. Based on the return value of compareSub, the algorithm adjusts the left and right pointers:

If compareSub returns 0, this means the sums of the first and second thirds are equal, implying that the unique element is not in either of the first two thirds. Thus, the algorithm eliminates these two segments from consideration by setting left to t3 + 1.
If compareSub returns 1, this indicates that the first third contains the unique element, so the right pointer is adjusted to t2 to discard the latter two-thirds of the search space.
If compareSub returns -1, this shows that the unique element is in the second third, and the search space is updated by setting left to t2 + 1 and right to t3.

The loop continues until left equals right, which means the search space has been narrowed down to a single element—the unique element that is larger than the others. At this point, the algorithm returns left, the index of the unique element.

This approach ensures that the search space is halved at each step, making it possible to find the element within a logarithmic number of comparisons, specifically log3(n), where n is the length of the array. Using ternary search instead of binary search allows us to reduce the number of necessary comparisons, capitalizing on the specific nature of the problem.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider that we have an ArrayReader that represents the following array: [1, 1, 1, 2, 1, 1, 1, 1]. We need to find the index of the element that is larger than the rest using the solution approach described above.

We have a total of 8 elements in the array, so our initial left is 0 and our right is 7.

Initially, t1 = left = 0.
t2 = left + (right - left) // 3 = 0 + (7 - 0) // 3 = 2.
t3 = left + 2 * ((right - left) // 3) + 1 = 0 + 2 * ((7 - 0) // 3) + 1 = 5.

We call compareSub(0, 2, 3, 5) and suppose it returns 0, meaning the sum of elements from index 0 to 2 is the same as the sum of elements from index 3 to 5. Therefore, our unique element must be in the last third of the array.

So now, we update left to t3 + 1 = 6.

On the next iteration:

t1 = left = 6.
Since right remains the same, we calculate t2 and t3 within the new bounds.
t2 = left + (right - left) // 3 = 6 + (7 - 6) // 3 = 6.
t3 = left + 2 * ((right - left) // 3) + 1 = 6 + 2 * ((7 - 6) // 3) + 1 = 7.

We call compareSub(6, 6, 7, 7) and it can only return 1, because the unique larger element must be at index 7 (since 6 and 6 are the same index, and the only remaining index is 7).

Now that left and right have converged (both are 7), we found our unique larger value at the index 7. We return 7.

This example demonstrates that by narrowing down the search space with each comparison and adjusting the pointers accordingly, we can find the index of the unique larger element with a minimal number of calls to the API, satisfying our constraints.

Solution Implementation

1class Solution:
2    def getIndex(self, reader: 'ArrayReader') -> int:
3        # Initialize two pointers for binary search
4        left, right = 0, reader.length() - 1
5
6        while left < right:
7            # Divide the range into three equal parts
8            # and determine their endpoints
9            one_third = (right - left) // 3
10            two_thirds = 2 * one_third
11
12            first_part_end = left + one_third
13            second_part_start = first_part_end + 1
14            second_part_end = left + two_thirds
15            third_part_start = second_part_end + 1
16          
17            # Compare the sum of the first third with the sum of the second third
18            comparison_result = reader.compareSub(left, first_part_end, second_part_start, second_part_end)
19          
20            # If both sums are equal, the pivot index must be in the third part
21            if comparison_result == 0:
22                left = third_part_start
23            # If the sum of the first third is greater, the pivot index is in the first part
24            elif comparison_result == 1:
25                right = first_part_end
26            # If the sum of the second third is greater, the pivot index is in the second part
27            else:
28                left, right = second_part_start, second_part_end
29
30        # When 'left' is equal to 'right', we have found the pivot index
31        return left
32

1class Solution {
2    public int getIndex(ArrayReader reader) {
3        // Initialize pointers for left and right boundaries
4        int left = 0;
5        int right = reader.length() - 1;
6
7        // Use a modified version of binary search to find the specific index
8        while (left < right) {
9            // Divide the range into three equal parts
10            int mid1 = left + (right - left) / 3;
11            int mid2 = left + (right - left) / 3 * 2 + 1;
12          
13            // Compare the sum of the first two-thirds with the sum of the last two-thirds
14            int comparisonResult = reader.compareSub(left, mid1, mid1 + 1, mid2);
15            // If the sums are equal, the desired index is in the last third
16            if (comparisonResult == 0) {
17                left = mid2 + 1;
18            // If the sum of the first third is greater, the desired index is in the first third
19            } else if (comparisonResult == 1) {
20                right = mid1;
21            // Otherwise, the desired index is in the middle third
22            } else {
23                left = mid1 + 1;
24                right = mid2;
25            }
26        }
27        // Left should now be the desired index as the range has been narrowed down to a single element
28        return left;
29    }
30}
31

1class Solution {
2public:
3    // Assuming the array contains a peak element (an element that is greater
4    // than its neighbours), this function finds the index of one such peak element.
5    int getIndex(ArrayReader& reader) {
6        int left = 0; // Begin search at the start of the array
7        int right = reader.length() - 1; // End search at the last element of the array
8
9        // Continue searching while the range is not narrowed down to one element
10        while (left < right) {
11            // Divide the current range into three equal parts
12            int part1End = left + (right - left) / 3;
13            int part2Start = part1End + 1;
14            int part2End = left + (right - left) / 3 * 2;
15            int part3Start = part2End + 1;
16
17            // Compare sum of elements in the first and second parts
18            int comparisonResult = reader.compareSub(left, part1End, part2Start, part2End);
19
20            if (comparisonResult == 0) {
21                // If sums are equal, the peak must be in the third part, discard first two parts
22                left = part3Start;
23            } else if (comparisonResult == 1) {
24                // If sum of first part is greater, the peak is in the first part, discard the rest
25                right = part1End;
26            } else {
27                // If sum of second part is greater, the peak is between part2Start and part2End,
28                // discard the parts outside of this range
29                left = part2Start;
30                right = part2End;
31            }
32        }
33
34        // The narrowed down range will eventually converge to a single element.
35        // This element is a peak (a candidate index where the element is not smaller than its neighbors).
36        return left;
37    }
38};
39

1// Function to find the index of one peak element.
2// A peak element is greater than its neighbors.
3function getIndex(reader: { length: () => number, compareSub: (start1: number, end1: number, start2: number, end2: number) => number }): number {
4    let left = 0; // Start of the search range
5    let right = reader.length() - 1; // End of the search range
6
7    // Continue search while there is more than one element in the range
8    while (left < right) {
9        // Divide the current range into three equal parts
10        const part1End = left + Math.floor((right - left) / 3);
11        const part2Start = part1End + 1;
12        const part2End = left + Math.floor((right - left) / 3 * 2);
13        const part3Start = part2End + 1;
14
15        // Compare the sum of elements in the first and second parts
16        const comparisonResult = reader.compareSub(left, part1End, part2Start, part2End);
17
18        if (comparisonResult === 0) {
19            // Sums are equal, peak must be in the third part
20            left = part3Start;
21        } else if (comparisonResult === 1) {
22            // Sum of first part is greater, peak is in the first part
23            right = part1End;
24        } else {
25            // Sum of second part is greater, peak is in between part2Start and part2End
26            left = part2Start;
27            right = part2End;
28        }
29    }
30
31    // Once the range is narrowed down to one element, return it
32    // This element is not guaranteed to be a peak, but based on the problem
33    // statement it is considered as a correct answer.
34    return left;
35}
36

Time and Space Complexity

The given code uses a ternary search approach to find an index in a simulated array using the ArrayReader API. The while loop repeatedly narrows down the search range by dividing it into thirds and comparing the sums of different segments of the array.

Time Complexity:

The time complexity is O(log3(n)), where n is the length of the array. In each iteration of the loop, the size of the current search range is reduced by 1/3. Since we are making two calls to compareSub per iteration, these calls do not significantly increase the time complexity, and the dominating factor remains the division by three in each step. The complexity is determined by how many times we can divide the range length by 3 until we reach a range of length 1.

Space Complexity:

The space complexity is O(1) because no additional space is allocated proportional to the input size. The algorithm only uses a fixed number of variables to store the indices (left, right, t1, t2, and t3) and the comparison result cmp regardless of the size of the array.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What are the two properties the problem needs to have for dynamic programming to be applicable? (Select 2)

Optimal substructure

Overlapping subproblems

Non-overlapping subproblems

Constant time subproblems