Threshold Majority Queries - Solution & Explanation

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.