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.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.
Preprocess the input array to create a map that keeps count of the index positions for each element. Use this map to efficiently determine the count of an element in any given subarray, enabling quick queries for the majority element.
This solution uses a defaultdict to store the indices of each element in the array. When a query is made, it checks possible candidates based on the existing numbers in the subarray, and verifies their frequency using binary search to locate their positions quickly.
Python
JavaScript
Time Complexity: O(n log n) for preprocessing and O(k log m) for each query, where k is the number of unique elements in the subarray and m is their frequency. Space Complexity: O(n), where n is the length of the array due to storage of indices.
Use a segment tree to preprocess the given array. Each node in the segment tree maintains information about the majority element in that segment along with its frequency. Lazy propagation is used to efficiently update ranges during queries.
Here, a segment tree is used to preprocess the array. Each node represents the majority element of that segment and its frequency relative to the segment. During query operations, the segment tree quickly retrieves and recombines results for subarrays, updating only the segments that require attention, thus utilizing lazy evaluation with a complexity close to logarithmic.
Time Complexity: O(n) to build the segment tree and O(log n + k) for each query, where k is the number of operations merged. Space Complexity: O(n) due to extra storage for the segment tree.
We notice that the problem requires us to find the possible majority element in a specific interval, so we consider using a segment tree to maintain the candidate majority element and its occurrence in each interval.
We define each node of the segment tree as Node, each node contains the following attributes:
l: The left endpoint of the node, the index starts from 1.r: The right endpoint of the node, the index starts from 1.x: The candidate majority element of the node.cnt: The occurrence of the candidate majority element of the node.The segment tree mainly has the following operations:
build(u, l, r): Build the segment tree.pushup(u): Use the information of the child nodes to update the information of the parent node.query(u, l, r): Query the interval sum.In the initialization method of the main function, we first create a segment tree, and use a hash table d to record all indexes of each element in the array.
In the query(left, right, threshold) method, we directly call the query method of the segment tree to get the candidate majority element x. Then use binary search to find the first index l in the array that is greater than or equal to left, and the first index r that is greater than right. If r - l \ge threshold, return x, otherwise return -1.
In terms of time complexity, the time complexity of the initialization method is O(n), and the time complexity of the query method is O(log n). The space complexity is O(n). Here, n is the length of the array.
| Approach | Complexity |
|---|---|
| Hash Map with Preprocessing | Time Complexity: O(n log n) for preprocessing and O(k log m) for each query, where k is the number of unique elements in the subarray and m is their frequency. Space Complexity: O(n), where n is the length of the array due to storage of indices. |
| Segment Tree with Lazy Propagation | Time Complexity: O(n) to build the segment tree and O(log n + k) for each query, where k is the number of operations merged. Space Complexity: O(n) due to extra storage for the segment tree. |
| Segment Tree + Boyer-Moore Voting Algorithm + Binary Search | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Frequency Count | O(n) per query | O(1) | Small arrays or very few queries |
| Hash Map + Random Sampling + Binary Search | Expected O(log n) per query | O(n) | Practical solution with fast average performance |
| Segment Tree with Majority Candidate | O(log n) query, O(n) build | O(n) | Deterministic approach for many range queries |
Leetcode 1157. Online Majority Element In Subarray • coderZ • 1,124 views views
Watch 7 more video solutions →Practice Online Majority Element In Subarray with our built-in code editor and test cases.
Practice on FleetCode