Online Majority Element In Subarray - Video Solutions
Leetcode 1157. Online Majority Element In Subarray
Online Majority Element In Subarray - Video Solution
Watch 6 video solutions for Online Majority Element In Subarray, a hard level problem involving Array, Binary Search, Design. This walkthrough by coderZ has 1,145 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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 arrayarr.int query(int left, int right, int threshold)returns the element in the subarrayarr[left...right]that occurs at leastthresholdtimes, or-1if 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 + 1- At most
104calls will be made toquery.
Approach Overview
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.
Complexity Analysis
| 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 |