Online Majority Element In Subarray

Online Majority Element In Subarray

What is this problem about?

The Online Majority Element In Subarray problem asks you to design a data structure supporting queries: given a subarray [left, right] and a threshold, find the element that appears > threshold * (right-left+1) times, or -1 if none exists. This hard design problem uses binary search on precomputed candidate positions. The array, design, binary search, binary indexed tree, and segment tree interview pattern is the core.

Why is this asked in interviews?

Nutanix asks this hard design problem because it requires preprocessing candidate majority elements efficiently for online range queries. Boyer-Moore majority vote on the full array narrows candidates, but range queries need per-candidate position lists and binary search for verification.

Algorithmic pattern used

Precomputed candidate positions + binary search + frequency count. During initialization: for each element value, store its sorted list of positions. For a query [l, r, threshold]: use a segment tree to find the majority element candidate in [l,r] (via Boyer-Moore reduction on segments). Verify the candidate by counting its occurrences in [l,r] using binary search on its position list. If count > threshold*(r-l+1), return candidate; else -1.

Example explanation

Array=[1,2,3,2,2]. Query(1,4,0.5): subarray=[2,3,2,2], length=4, threshold count > 2. Candidate: Boyer-Moore on [2,3,2,2] → 2. Positions of 2: [1,3,4]. Count in [1,4]: bisect_right(5)-bisect_left(1)=3. 3>2 ✓. Return 2.

Common mistakes candidates make

• Not building candidate position lists for O(log n) verification.
• Using linear scan to count candidate occurrences (O(n) per query).
• Boyer-Moore selection on subarrays without segment tree support.
• Not handling the case where the candidate fails verification (return -1).

Interview preparation tip

Hard design problems require combining multiple data structures. Here: segment tree for majority candidate selection + sorted lists + binary search for verification. Each component should be practiced independently. Segment tree "majority voting" merge operation is the key non-trivial component. Practice designing offline and online range query structures for statistics like majority, median, and mode.