Back

3955. Threshold Majority Queries

Hard
Array
Hash Table
Binary Search
Divide and Conquer
Counting
Prefix Sum
Solve on LeetCode View Solutions

Description

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 <= 104
  • 1 <= nums[i] <= 109
  • 1 <= queries.length <= 5 * 104
  • queries[i] = [li, ri, thresholdi]
  • 0 <= li <= ri < n
  • 1 <= thresholdi <= ri - li + 1

Hints

Hint 1
Use sqrt decomposition: let <code>B = int(sqrt(n))</code> and sort queries by <code>(l//B, r)</code>
Hint 2
Maintain window <code>[L,R]</code> with a frequency map <code>cnt</code> and buckets <code>bucket[f]</code> of values at count <code>f</code>
Hint 3
Slide <code>L</code> and <code>R</code> per query, updating <code>cnt</code> and <code>bucket</code>, then scan from <code>threshold</code> to max freq to find the smallest valid value or -1

Statistics

Acceptance
21.5%
Submissions
20,585
Accepted
4,423