Skip to main content
Talentd

Find the Index of the Large Integer - Solution & Explanation

MediumPremiumFree on FleetCodeArrayBinary SearchInteractive7 min readAsked at: Amazon
Practice this problem

Problem Statement

We have an integer array arr, where all the integers in arr are equal except for one integer which is larger than the rest of the integers. You will not be given direct access to the array, instead, you will have an API ArrayReader which have the following functions:

  • int compareSub(int l, int r, int x, int y): where 0 <= l, r, x, y < ArrayReader.length(), l <= r and x <= y. The function compares the sum of sub-array arr[l..r] with the sum of the sub-array arr[x..y] and returns:
    • 1 if arr[l]+arr[l+1]+...+arr[r] > arr[x]+arr[x+1]+...+arr[y].
    • 0 if arr[l]+arr[l+1]+...+arr[r] == arr[x]+arr[x+1]+...+arr[y].
    • -1 if arr[l]+arr[l+1]+...+arr[r] < arr[x]+arr[x+1]+...+arr[y].
  • int length(): Returns the size of the array.

You are allowed to call compareSub() 20 times at most. You can assume both functions work in O(1) time.

Return the index of the array arr which has the largest integer.

 

Example 1:

Input: arr = [7,7,7,7,10,7,7,7]
Output: 4
Explanation: The following calls to the API
reader.compareSub(0, 0, 1, 1) // returns 0 this is a query comparing the sub-array (0, 0) with the sub array (1, 1), (i.e. compares arr[0] with arr[1]).
Thus we know that arr[0] and arr[1] doesn't contain the largest element.
reader.compareSub(2, 2, 3, 3) // returns 0, we can exclude arr[2] and arr[3].
reader.compareSub(4, 4, 5, 5) // returns 1, thus for sure arr[4] is the largest element in the array.
Notice that we made only 3 calls, so the answer is valid.

Example 2:

Input: nums = [6,6,12]
Output: 2

 

Constraints:

  • 2 <= arr.length <= 5 * 105
  • 1 <= arr[i] <= 100
  • All elements of arr are equal except for one element which is larger than all other elements.

 

Follow up:

  • What if there are two numbers in arr that are bigger than all other numbers?
  • What if there is one number that is bigger than other numbers and one number that is smaller than other numbers?

Approach Overview

Problem Overview: You are given an array where every value is equal except one element that is strictly larger. Direct access to the array is not allowed. Instead, an ArrayReader API compares the sum of two subarrays. The task is to locate the index of the larger element using as few comparisons as possible.

Approach 1: Linear Comparison with compareSub (O(n) time, O(1) space)

The simplest strategy repeatedly compares single elements using the compareSub API. Start with index 0 as the current candidate. Compare [candidate, candidate] with [i, i] for every i from 1 to n-1. If the result shows the right side is larger, update the candidate. This effectively simulates a linear scan over the array using the provided comparison interface. Time complexity is O(n) API calls with O(1) extra space. It works but wastes comparisons and is rarely expected in interviews.

Approach 2: Binary Search with Subarray Comparison (O(log n) time, O(1) space)

The optimal solution leverages the fact that all elements except one are identical. Split the array into two equal halves and compare their sums using compareSub(l, mid, mid+1, r). If the sums are equal, the larger element must be outside those ranges (which only happens when the length is odd and the middle element is excluded). If the left half is larger, the target index lies in that half; otherwise it lies in the right half. This turns the search into a classic binary search style narrowing process.

When the subarray length is odd, exclude the middle element during the comparison so both halves have equal length. If the sums match, the excluded middle index is the answer. Otherwise continue searching in the heavier half. Each step cuts the search space roughly in half while making a constant number of calls to the compareSub API.

This approach relies on reasoning about sums rather than direct element access, a common pattern in interactive problems. Because each comparison eliminates half the candidates, the total number of queries is O(log n) with constant auxiliary memory.

Recommended for interviews: The binary search strategy is the expected solution. A linear scan shows you understand how to use the API, but interviewers look for the observation that equal values allow sum comparisons to reveal which half contains the larger element. Reducing the search space with compareSub demonstrates algorithmic reasoning and efficient query usage.

Solution

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Linear Comparison using compareSubO(n)O(1)Simple baseline when optimizing query count is not required
Binary Search with Subarray Sum ComparisonO(log n)O(1)Optimal approach for interactive constraints and minimal API calls

Video Solution

1533. Find the Index of the Large Integer - Week 3/5 Leetcode January Challenge • Programming Live with Larry • 363 views views

Watch 2 more video solutions →

Frequently Asked Questions

Is Find the Index of the Large Integer easy or hard?
The problem is rated Medium because the algorithm itself is simple once the insight is clear. The challenge comes from the interactive API and reasoning about subarray sums instead of accessing elements directly.
Find the Index of the Large Integer Python/Java solution
Implement a binary search loop that repeatedly calls reader.compareSub on two equal segments. Adjust the left and right pointers based on which side has the larger sum until only one index remains. The same logic translates directly to Python, Java, C++, and Go.
How to solve Find the Index of the Large Integer in O(log n)?
Split the array into two equal halves and compare their sums using compareSub. If the left half has a larger sum, the large integer lies there; if the right half is larger, search that side. When the range length is odd, skip the middle element during comparison and check it if both halves match.
What is the best approach for Find the Index of the Large Integer?
Binary search with subarray sum comparison is the best approach. Using the ArrayReader compareSub API, you compare two equal-sized halves of the array and discard the smaller side. Each query eliminates half the search space, giving O(log n) comparisons and O(1) extra space.
Is Find the Index of the Large Integer asked at Google/Amazon/Meta?
Interactive binary search problems like this appear in interviews at companies such as Google and Meta because they test reasoning under restricted access. The problem evaluates how efficiently you reduce search space using limited queries.
What data structure is used in Find the Index of the Large Integer?
The problem conceptually uses an array, but direct access is restricted. The key technique is binary search combined with an interactive comparison API that returns the relative sum of two subarrays.
What is the time complexity of Find the Index of the Large Integer?
The optimal solution runs in O(log n) time because each compareSub operation halves the remaining search range. Only a constant amount of extra memory is used, so the space complexity is O(1).

Ready to solve this problem?

Practice Find the Index of the Large Integer with our built-in code editor and test cases.

Practice on FleetCode
Previous

Search in a Sorted Array of Unknown Size