We have an integer array nums, where all the integers in nums are 0 or 1. You will not be given direct access to the array, instead, you will have an API ArrayReader which have the following functions:
int query(int a, int b, int c, int d): where 0 <= a < b < c < d < ArrayReader.length(). The function returns the distribution of the value of the 4 elements and returns:
int length(): Returns the size of the array.You are allowed to call query() 2 * n times at most where n is equal to ArrayReader.length().
Return any index of the most frequent value in nums, in case of tie, return -1.
Example 1:
Input: nums = [0,0,1,0,1,1,1,1] Output: 5 Explanation: The following calls to the API reader.length() // returns 8 because there are 8 elements in the hidden array. reader.query(0,1,2,3) // returns 2 this is a query that compares the elements nums[0], nums[1], nums[2], nums[3] // Three elements have a value equal to 0 and one element has value equal to 1 or viceversa. reader.query(4,5,6,7) // returns 4 because nums[4], nums[5], nums[6], nums[7] have the same value. we can infer that the most frequent value is found in the last 4 elements. Index 2, 4, 6, 7 is also a correct answer.
Example 2:
Input: nums = [0,0,1,1,0] Output: 0
Example 3:
Input: nums = [1,0,1,0,1,0,1,0] Output: -1
Constraints:
5 <= nums.length <= 1050 <= nums[i] <= 1
Follow up: What is the minimum number of calls needed to find the majority element?
Problem Overview: You interact with a hidden binary array where direct access is not allowed. Instead, an API query(a,b,c,d) returns a value (0, 2, or 4) describing how many elements among the four indices share the same value. The task is to identify an index belonging to the majority value in the array, or return -1 if the number of 0s and 1s are equal.
Approach 1: Brainteaser with Reference Queries (O(n) time, O(1) space)
The key idea is to classify every index relative to a known reference element using carefully chosen queries. Start with a baseline query q = query(0,1,2,3). This result establishes a pattern for the first four indices. For every new index i, run a query that replaces one element of the baseline group (for example query(1,2,3,i)). If the result matches the baseline pattern, nums[i] has the same value as nums[0]; otherwise it belongs to the opposite group.
For the first few elements (indices 1–3), additional comparison queries determine whether they match the value at index 0. After establishing this relationship, iterate through the rest of the array and classify each index into either the "same as index 0" group or the "different" group. Maintain counts for both groups and store at least one representative index from each.
Once all indices are classified, compare the group sizes. If both groups contain the same number of elements, no majority exists and the answer is -1. Otherwise, return any index from the larger group. This strategy works because each query effectively reveals whether the new index preserves the equality pattern of the reference quadruple.
The algorithm performs a constant number of queries for the first few indices and then one query per remaining index, leading to O(n) total queries and O(1) extra memory. The trick is recognizing that a single baseline comparison lets you infer relative equality across the entire array without ever seeing the values directly.
Recommended for interviews: The expected solution is the brainteaser-style reference comparison method. Interviewers want to see whether you can reason about information gained from each query and reduce the problem to grouping indices relative to a fixed reference. The approach combines logical deduction with careful query reuse, a common pattern in interactive problems. Understanding how the hidden structure behaves also relies on reasoning about arrays and parity-style patterns often seen in math puzzles.
We first call reader.query(0, 1, 2, 3) and record the result as x.
Next, we iterate from index 4 onwards. Each time we call reader.query(0, 1, 2, i), if the result is the same as x, we increment a by one; otherwise, we increment b by one and update k to i.
Then, we need to check whether the elements at indices 0, 1, 2 are the same as the element at index 3. If they are the same, we increment a by one; otherwise, we increment b by one and update k to the corresponding index.
Finally, if a = b, it means the number of 0s and 1s in the array are equal, so we return -1; otherwise, if a > b, we return 3, otherwise we return k.
The time complexity is O(n), where n is the length of the array. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Naive Guessing / Random Queries | O(n²) queries | O(1) | Conceptual baseline; repeatedly compare groups without a fixed reference |
| Brainteaser with Reference Query Pattern | O(n) queries | O(1) | Optimal solution; classify every index relative to a baseline query |
1538. Guess the Majority in a Hidden Array - Week 5/5 Leetcode April Challenge • Programming Live with Larry • 323 views views
Watch 1 more video solutions →Practice Guess the Majority in a Hidden Array with our built-in code editor and test cases.
Practice on FleetCode