Online Majority Element In Subarray - Video Solutions

Problem Overview: You receive an integer array and many queries of the form (left, right, threshold). For each query, return the element that appears at least threshold times inside the subarray arr[left...right]. If no such element exists, return -1. Since queries are online and frequent, repeatedly scanning the subarray is too slow.

Approach 1: Hash Map with Preprocessing + Binary Search (Average O(log n) per query, O(n) space)

Preprocess the array using a hash map that stores a sorted list of indices for every distinct value. This allows you to count how many times a value appears inside any range using binary search. During a query, randomly sample a few indices from the range [left, right]. Each sampled value becomes a candidate majority. Use binary search on its index list to count occurrences inside the range and check whether it meets the threshold. Each verification takes O(log n), and sampling a small constant number of candidates keeps the expected query time close to O(log n). This approach relies on the probability that a true majority element will be sampled quickly.

The key idea is fast frequency verification. The hash map stores value → sorted indices, and binary search finds the first and last positions inside the query range. You avoid scanning the entire subarray while still confirming exact counts. This technique combines array preprocessing with binary search for efficient range counting.

Approach 2: Segment Tree with Majority Candidate (O(log n) query, O(n) space)

A more deterministic solution builds a segment tree. Each node stores a candidate element and a relative count using the Boyer–Moore majority merge idea. When combining two segments, if both candidates match, their counts add; otherwise the larger count survives after subtraction. This process propagates a potential majority candidate upward.

For a query range, the segment tree returns a candidate in O(log n). That candidate may not actually meet the threshold, so verify it using the same preprocessing map of value → sorted indices. Counting occurrences with binary search takes O(log n). The overall query cost becomes O(log n) with reliable worst‑case behavior.

This design separates two responsibilities: the segment tree quickly proposes a candidate, while the index map verifies its true frequency. The tree handles range queries efficiently, and binary search provides exact counts without scanning the array.

Recommended for interviews: Start by explaining why brute force O(n) per query is too slow when queries are large. Then move to the segment tree approach. Interviewers typically expect a range-query structure combined with frequency verification. The hash map preprocessing shows good practical optimization, while the segment tree demonstrates strong understanding of range data structures.