Threshold Majority Queries solution and explanation
Google
2 more videos on this problem
3636. Threshold Majority Queries (Leetcode Hard)Programming Live with Larry · 1:58:36 · 393 views
Threshold Majority Queries (PART 1) | LeetCode 3636 (HARD) | Mo's Algorithm | Square Root Decompo...codemintt · 1:14:07 · 199 views
Threshold Majority Queries(PART 2)| LeetCode 3636 (HARD) | MO's algorithm | Square-Root-Decomositioncodemintt · 9:46 · 85 views
The problem
You are given an integer array nums of length n and an array queries, where queries[i] = [li, ri, thresholdi].
Return an array of integers ans where ans[i] is equal to the element in the subarray nums[li...ri] that appears at least thresholdi times, selecting the element with the highest frequency (choosing the smallest in case of a tie), or -1 if no such element exists.
Example 1:
Input: nums = [1,1,2,2,1,1], queries = [[0,5,4],[0,3,3],[2,3,2]]
Output: [1,-1,2]
Explanation:
| Query | Sub-array | Threshold | Frequency table | Answer |
|---|---|---|---|---|
| [0, 5, 4] | [1, 1, 2, 2, 1, 1] | 4 | 1 → 4, 2 → 2 | 1 |
| [0, 3, 3] | [1, 1, 2, 2] | 3 | 1 → 2, 2 → 2 | -1 |
| [2, 3, 2] | [2, 2] | 2 | 2 → 2 | 2 |
Example 2:
Input: nums = [3,2,3,2,3,2,3], queries = [[0,6,4],[1,5,2],[2,4,1],[3,3,1]]
Output: [3,2,3,2]
Explanation:
| Query | Sub-array | Threshold | Frequency table | Answer |
|---|---|---|---|---|
| [0, 6, 4] | [3, 2, 3, 2, 3, 2, 3] | 4 | 3 → 4, 2 → 3 | 3 |
| [1, 5, 2] | [2, 3, 2, 3, 2] | 2 | 2 → 3, 3 → 2 | 2 |
| [2, 4, 1] | [3, 2, 3] | 1 | 3 → 2, 2 → 1 | 3 |
| [3, 3, 1] | [2] | 1 | 2 → 1 | 2 |
Constraints:
1 <= nums.length == n <= 1041 <= nums[i] <= 1091 <= queries.length <= 5 * 104queries[i] = [li, ri, thresholdi]0 <= li <= ri < n1 <= thresholdi <= ri - li + 1
Approach overview
Problem Overview: You are given an array and multiple queries. Each query specifies a range [l, r] and a threshold. The task is to return any value that appears at least threshold times inside that subarray. If no such element exists, return -1. The difficulty comes from answering many range queries efficiently while verifying frequency constraints.
Approach 1: Brute Force Counting (O(n) per query, O(1) space)
For each query, iterate through the subarray [l, r] and count frequencies using a temporary hash map. As soon as a value reaches the required threshold, return it. This approach is straightforward and demonstrates the core requirement: verifying whether any value meets the frequency constraint. However, in the worst case every query scans the entire range, giving O(n) time per query and O(n · q) overall. With large input sizes this quickly becomes too slow.
Approach 2: Segment Tree Majority Candidate + Binary Search Verification (O((n + q) log n) time, O(n) space)
The optimized approach separates the problem into two steps: quickly finding a candidate and efficiently verifying its frequency. Build a segment tree where each node stores a majority candidate for its segment using the Boyer–Moore voting merge rule. When two segments combine, keep the candidate that survives the vote cancellation process. This gives a potential majority element for any queried range in O(log n) time.
The candidate alone is not enough because the query requires a threshold count, not necessarily a strict majority. To verify the candidate, maintain a hash map from value → sorted list of indices where it appears. After retrieving the candidate from the segment tree, use binary search to count how many occurrences fall within [l, r]. Two binary searches (lower_bound and upper_bound) give the frequency in O(log n). If the count meets the threshold, return the candidate; otherwise return -1.
This combination works because the segment tree quickly narrows the possible answer, while the index lists provide accurate counting. The preprocessing cost is linear and each query stays logarithmic.
Recommended for interviews: Interviewers typically expect the segment tree + verification strategy. The brute force solution shows you understand the frequency requirement, but it does not scale. The optimized method demonstrates practical use of divide and conquer through segment trees, plus efficient frequency counting with hash tables and binary search.
The written solution for this problem is still being prepared. Try it yourself in the meantime.
Try solving it yourselfComplexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Frequency Count | O(n · q) | O(n) | Small inputs or when the number of queries is very low |
| Segment Tree Candidate + Binary Search Verification | O((n + q) log n) | O(n) | Large arrays and many queries requiring fast range processing |
Frequently asked questions
Is Threshold Majority Queries easy or hard?
Threshold Majority Queries is considered a hard problem because it combines multiple advanced ideas: range queries, candidate majority detection, and efficient frequency verification. Implementing the segment tree merge logic and binary search counting correctly requires strong data structures knowledge.
Threshold Majority Queries Python/Java solution
Typical implementations build the segment tree and maintain a dictionary or map from value to sorted indices. Queries fetch a candidate from the tree and verify frequency using binary search. The same algorithm works in Python, Java, C++, and Go with similar O((n + q) log n) complexity.
What is the best approach for Threshold Majority Queries?
The most practical approach uses a segment tree to retrieve a majority candidate for any range and then verifies its frequency using binary search on precomputed index lists. Each query runs in O(log n) time and preprocessing takes O(n). This approach scales well for large arrays and many queries.
Is Threshold Majority Queries asked at Google/Amazon/Meta?
Range frequency and majority query problems appear in interviews at large companies including Google, Amazon, and Meta. Variants often test segment trees, divide and conquer strategies, and efficient counting within subarrays.
What data structure is used in Threshold Majority Queries?
The optimized solution combines multiple structures: a segment tree for range candidate queries, a hash map mapping values to sorted index lists, and binary search to count occurrences within a range.
What is the time complexity of Threshold Majority Queries?
Using a segment tree with binary search verification, preprocessing takes O(n) and each query takes O(log n). Overall complexity is O((n + q) log n). A naive brute force approach requires O(n) work per query, which becomes O(n · q).
How to solve Threshold Majority Queries in O((n + q) log n)?
Build a segment tree that stores a candidate majority element for each range using Boyer–Moore style merging. For each query, retrieve the candidate in O(log n). Then count its occurrences in the query range using two binary searches on a precomputed list of positions for that value.