Guess the Majority in a Hidden Array - Solution & Explanation
Problem Statement
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): where0 <= a < b < c < d < ArrayReader.length(). The function returns the distribution of the value of the 4 elements and returns:- 4 : if the values of the 4 elements are the same (0 or 1).
- 2 : if three elements have a value equal to 0 and one element has value equal to 1 or vice versa.
- 0 : if two element have a value equal to 0 and two elements have a value equal to 1.
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?
Approach Overview
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.
Solution
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).
Code
Python
Java
C++
Go
TypeScript
Detailed Complexity Analysis
| 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 |
Video Solution
1538. Guess the Majority in a Hidden Array - Week 5/5 Leetcode April Challenge • Programming Live with Larry • 325 views views
Watch 1 more video solutions →Frequently Asked Questions
Is Guess the Majority in a Hidden Array easy or hard?
Guess the Majority in a Hidden Array Python/Java solution
How to solve Guess the Majority in a Hidden Array in O(n)?
What is the best approach for Guess the Majority in a Hidden Array?
Is Guess the Majority in a Hidden Array asked at Google/Amazon/Meta?
What data structure is used in Guess the Majority in a Hidden Array?
What is the time complexity of Guess the Majority in a Hidden Array?
Ready to solve this problem?
Practice Guess the Majority in a Hidden Array with our built-in code editor and test cases.
Practice on FleetCode