How do you solve Threshold Majority Queries on LeetCode?

Threshold Majority Queries (LeetCode #3636) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n log n + q * (n/B + m)) time complexity and O(n) space complexity. Key insight: Using sqrt decomposition optimizes range queries.

What is the brute force solution for Threshold Majority Queries?

The brute force approach for Threshold Majority Queries is Brute Force, with O(n²) time complexity and O(1) space complexity. This approach checks each query independently by counting occurrences of each element in the specified subarray. It is straightforward but inefficient for large inputs. The optimal Optimal Solution approach improves this to O(n log n + q * (n/B + m)).

What are common mistakes when solving Threshold Majority Queries?

Not updating counts correctly when adjusting L and R.

#3636

Threshold Majority Queries

Hard

ArrayHash TableBinary SearchDivide and ConquerCountingPrefix Sum

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n log n + q * (n/B + m))
Space	O(1)	O(n)

💡

Intuition

Time O(n log n + q * (n/B + m))Space O(n)

Using sqrt decomposition, we can efficiently manage the frequency counts of elements in the subarrays, reducing the number of operations needed for each query.

⚙️

Algorithm

3 steps

1Step 1: Sort queries based on (l // B, r) where B is the block size (sqrt(n)).
2Step 2: Maintain a frequency map and a bucket for counts of elements as we adjust the current window [L, R] to match the query range.
3Step 3: For each query, check the frequency map to find the element meeting the threshold and return the result.

solution.py22 lines

1import math
2from collections import defaultdict
3
4def thresholdMajority(nums, queries):
5    n = len(nums)
6    B = int(math.sqrt(n))
7    queries = sorted(enumerate(queries), key=lambda x: (x[1][0] // B, x[1][1]))
8    ans = [-1] * len(queries)
9    count = defaultdict(int)
10    L, R = 0, -1
11    for idx, (l, r, threshold) in queries:
12        while R < r: R += 1; count[nums[R]] += 1
13        while R > r: count[nums[R]] -= 1; R -= 1
14        while L < l: count[nums[L]] -= 1; L += 1
15        while L > l: L -= 1; count[nums[L]] += 1
16        max_freq, result = 0, -1
17        for num, freq in count.items():
18            if freq >= threshold:
19                if freq > max_freq or (freq == max_freq and num < result):
20                    max_freq, result = freq, num
21        ans[idx] = result
22    return ans

ℹ

Complexity note: The complexity arises from sorting the queries and managing the frequency counts, where m is the number of unique elements in the current window.

1Using sqrt decomposition optimizes range queries.
2Maintaining a frequency map allows for quick access to counts.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.