Design a data structure that efficiently finds the majority element of a given subarray.
The majority element of a subarray is an element that occurs threshold times or more in the subarray.
Implementing the MajorityChecker class:
MajorityChecker(int[] arr) Initializes the instance of the class with the given array arr.int query(int left, int right, int threshold) returns the element in the subarray arr[left...right] that occurs at least threshold times, or -1 if no such element exists.Example 1:
Input ["MajorityChecker", "query", "query", "query"] [[[1, 1, 2, 2, 1, 1]], [0, 5, 4], [0, 3, 3], [2, 3, 2]] Output [null, 1, -1, 2] Explanation MajorityChecker majorityChecker = new MajorityChecker([1, 1, 2, 2, 1, 1]); majorityChecker.query(0, 5, 4); // return 1 majorityChecker.query(0, 3, 3); // return -1 majorityChecker.query(2, 3, 2); // return 2
Constraints:
1 <= arr.length <= 2 * 1041 <= arr[i] <= 2 * 1040 <= left <= right < arr.lengththreshold <= right - left + 12 * threshold > right - left + 1104 calls will be made to query.Online Majority Element In Subarray requires answering multiple queries asking whether a value appears at least threshold times within a subarray. Since queries are frequent, a brute force scan per query would be too slow.
A common strategy is to combine randomized candidate selection with preprocessed index lists. For each number in the array, store the positions where it appears. During a query, randomly sample indices from the range [left, right] to obtain candidate values. For each candidate, use binary search on its stored position list to count occurrences inside the range. If the count meets the threshold, that value is the majority element.
Another conceptual approach involves building a segment tree that tracks potential majority candidates using a Boyer–Moore style merge. Candidate verification is still done using binary search on position lists. Preprocessing takes O(n log n) or O(n) depending on the structure, while each query can be answered in roughly O(log n) expected time with small constant factors.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Randomized sampling + position lists with binary search | Preprocessing: O(n), Query: O(log n) expected | O(n) |
| Segment Tree with candidate verification | Build: O(n log n), Query: O(log n) | O(n) |
take U forward
Use these hints if you're stuck. Try solving on your own first.
What's special about a majority element ?
A majority element appears more than half the length of the array number of times.
If we tried a random index of the array, what's the probability that this index has a majority element ?
It's more than 50% if that array has a majority element.
Try a random index for a proper number of times so that the probability of not finding the answer tends to zero.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, this type of problem appears in advanced interview rounds because it combines range queries, probabilistic thinking, and data structures. It tests knowledge of segment trees, binary search, and efficient query processing.
Segment trees and indexed position lists are commonly used. Position lists enable fast frequency counting using binary search, while a segment tree can help maintain candidate majority elements across ranges.
A practical approach combines randomized sampling with preprocessed index lists for each value. Candidate elements are sampled from the query range and verified using binary search to count their occurrences. This allows queries to be answered efficiently without scanning the entire subarray.
Random sampling quickly identifies likely majority candidates from the query range. Since a true majority appears frequently, the probability of sampling it is high, and verification with binary search ensures correctness.