NeetCode #897LC-1538MediumMath & GeometryNC Algo100
← Back to All Problems#897 · #1538 · Guess the Majority in a Hidden Array(找出隐藏数组中出现次数最多的值)
📌 Problem Statement & Constraints
This is an interactive problem, so it cannot be run offline: the hidden binary array is only reachable through the provided
ArrayReader API. reader.length() returns n; reader.query(a, b, c, d) takes four strictly increasing indices 0 <= a < b < c < d < n and returns 4 if all four values are equal, 2 if exactly three are equal, and 0 if the four values split two-and-two. Return the index of any value that appears more than n / 2 times, or -1 if there is no majority. Constraints: 4 <= n <= 10^5, at most 2n calls to query.💡 Core Algorithmic Approaches
- A query never reveals the value of an index, only the distribution of four values. Comparing
query(0, 1, 2, 3)withquery(0, 1, 2, i)therefore tells whether indexihas the same value as index3: the two queries differ only by3versusi. - This partitions all indices into two pigeonholes: those equal to index
3and those different from it. By the pigeonhole principle, if a majority exists it must lie in the larger pigeonhole, and we never need to know which bit index3actually holds. - Classify indices
4 .. n-1by comparingquery(0, 1, 2, i)with the referencex = query(0, 1, 2, 3), counting the two groups and remembering one index from the second group. - Indices
0, 1, 2were part of the reference query, so classify them against a fresh referencey = query(0, 1, 2, 4): comparingquery(1, 2, 3, 4),query(0, 2, 3, 4)andquery(0, 1, 3, 4)againstyeach isolates whether0,1or2matches index3. - If the two group sizes are equal there is no majority, so return
-1; otherwise return index3or the remembered index from the larger group.
💻 Benchmark Python3 Implementation
# This problem is interactive: `reader` is supplied by the judge and cannot be
# exercised offline. The API is:
# reader.length() -> int
# reader.query(a, b, c, d) -> 4 (all equal) / 2 (three equal) / 0 (two and two)
class Solution:
def guessMajority(self, reader: "ArrayReader") -> int:
n = reader.length()
# group A: indices with the same value as index 3; group B: the rest
a, b = 1, 0
k = -1 # one index from group B
ref = reader.query(0, 1, 2, 3)
for i in range(4, n):
if reader.query(0, 1, 2, i) == ref:
a += 1 # same value as index 3
else:
b += 1
k = i
# classify indices 0, 1, 2 using a reference that does not involve index 3
ref2 = reader.query(0, 1, 2, 4)
if reader.query(1, 2, 3, 4) == ref2: # differ only at 0 vs 3
a += 1
else:
b += 1
k = 0
if reader.query(0, 2, 3, 4) == ref2: # differ only at 1 vs 3
a += 1
else:
b += 1
k = 1
if reader.query(0, 1, 3, 4) == ref2: # differ only at 2 vs 3
a += 1
else:
b += 1
k = 2
if a == b:
return -1 # tie -> no majority
return 3 if a > b else k⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n) calls to query: one reference plus n - 4 classifications plus four extra queries, well within the 2n budget.
💾 Space Complexity
O(1): a few counters and indices.
⚠️ Interview Pitfalls & Follow-ups
- Trying to learn an index's value directly:
queryonly exposes the distribution of four values, never a single value. - Comparing
query(0, 1, 2, i)againstquery(0, 1, 2, j): that tests whetheriandjagree with each other, not whether they agree with index3; the reference must include index3. - Forgetting that indices
0, 1, 2belong to the reference group: they cannot be classified with thequery(0, 1, 2, i)trick, since they are inside that query, so a second reference is needed. - Returning a group index on a tie: when the two groups are equal there is no majority and the required answer is
-1. - Assuming
n < 4: the query API needs four distinct indices, so the problem guaranteesn >= 4.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.