3636. Threshold Majority Queries Hard
1/**
2 * [3636] Threshold Majority Queries
3 *
4 * You are given an integer array nums of length n and an array queries, where queries[i] = [li, ri, thresholdi].
5 * Return an array of integers <code data-end="33" data-start="28">ans where <code data-end="48" data-start="40">ans[i] is equal to the element in the subarray <code data-end="102" data-start="89">nums[li...ri] that appears at least <code data-end="137" data-start="125">thresholdi times, selecting the element with the highest frequency (choosing the smallest in case of a tie), or -1 if no such element exists.
6 *
7 * <strong class="example">Example 1:
8 * <div class="example-block">
9 * Input: <span class="example-io">nums = [1,1,2,2,1,1], queries = [[0,5,4],[0,3,3],[2,3,2]]</span>
10 * Output: <span class="example-io">[1,-1,2]</span>
11 * Explanation:
12 * <table style="border: 1px solid black;">
13 * <thead>
14 * <tr>
15 * <th align="left" style="border: 1px solid black;">Query</th>
16 * <th align="left" style="border: 1px solid black;">Sub-array</th>
17 * <th align="left" style="border: 1px solid black;">Threshold</th>
18 * <th align="left" style="border: 1px solid black;">Frequency table</th>
19 * <th align="left" style="border: 1px solid black;">Answer</th>
20 * </tr>
21 * </thead>
22 * <tbody>
23 * <tr>
24 * <td align="left" style="border: 1px solid black;">[0, 5, 4]</td>
25 * <td align="left" style="border: 1px solid black;">[1, 1, 2, 2, 1, 1]</td>
26 * <td align="left" style="border: 1px solid black;">4</td>
27 * <td align="left" style="border: 1px solid black;">1 → 4, 2 → 2</td>
28 * <td align="left" style="border: 1px solid black;">1</td>
29 * </tr>
30 * <tr>
31 * <td align="left" style="border: 1px solid black;">[0, 3, 3]</td>
32 * <td align="left" style="border: 1px solid black;">[1, 1, 2, 2]</td>
33 * <td align="left" style="border: 1px solid black;">3</td>
34 * <td align="left" style="border: 1px solid black;">1 → 2, 2 → 2</td>
35 * <td align="left" style="border: 1px solid black;">-1</td>
36 * </tr>
37 * <tr>
38 * <td align="left" style="border: 1px solid black;">[2, 3, 2]</td>
39 * <td align="left" style="border: 1px solid black;">[2, 2]</td>
40 * <td align="left" style="border: 1px solid black;">2</td>
41 * <td align="left" style="border: 1px solid black;">2 → 2</td>
42 * <td align="left" style="border: 1px solid black;">2</td>
43 * </tr>
44 * </tbody>
45 * </table>
46 * </div>
47 * <strong class="example">Example 2:
48 * <div class="example-block">
49 * Input: <span class="example-io">nums = [3,2,3,2,3,2,3], queries = [[0,6,4],[1,5,2],[2,4,1],[3,3,1]]</span>
50 * Output: <span class="example-io">[3,2,3,2]</span>
51 * Explanation:
52 * <table style="border: 1px solid black;">
53 * <thead>
54 * <tr>
55 * <th align="left" style="border: 1px solid black;">Query</th>
56 * <th align="left" style="border: 1px solid black;">Sub-array</th>
57 * <th align="left" style="border: 1px solid black;">Threshold</th>
58 * <th align="left" style="border: 1px solid black;">Frequency table</th>
59 * <th align="left" style="border: 1px solid black;">Answer</th>
60 * </tr>
61 * </thead>
62 * <tbody>
63 * <tr>
64 * <td align="left" style="border: 1px solid black;">[0, 6, 4]</td>
65 * <td align="left" style="border: 1px solid black;">[3, 2, 3, 2, 3, 2, 3]</td>
66 * <td align="left" style="border: 1px solid black;">4</td>
67 * <td align="left" style="border: 1px solid black;">3 → 4, 2 → 3</td>
68 * <td align="left" style="border: 1px solid black;">3</td>
69 * </tr>
70 * <tr>
71 * <td align="left" style="border: 1px solid black;">[1, 5, 2]</td>
72 * <td align="left" style="border: 1px solid black;">[2, 3, 2, 3, 2]</td>
73 * <td align="left" style="border: 1px solid black;">2</td>
74 * <td align="left" style="border: 1px solid black;">2 → 3, 3 → 2</td>
75 * <td align="left" style="border: 1px solid black;">2</td>
76 * </tr>
77 * <tr>
78 * <td align="left" style="border: 1px solid black;">[2, 4, 1]</td>
79 * <td align="left" style="border: 1px solid black;">[3, 2, 3]</td>
80 * <td align="left" style="border: 1px solid black;">1</td>
81 * <td align="left" style="border: 1px solid black;">3 → 2, 2 → 1</td>
82 * <td align="left" style="border: 1px solid black;">3</td>
83 * </tr>
84 * <tr>
85 * <td align="left" style="border: 1px solid black;">[3, 3, 1]</td>
86 * <td align="left" style="border: 1px solid black;">[2]</td>
87 * <td align="left" style="border: 1px solid black;">1</td>
88 * <td align="left" style="border: 1px solid black;">2 → 1</td>
89 * <td align="left" style="border: 1px solid black;">2</td>
90 * </tr>
91 * </tbody>
92 * </table>
93 * </div>
94 *
95 * Constraints:
96 *
97 * <li data-end="51" data-start="19"><code data-end="49" data-start="19">1 <= nums.length == n <= 10^4
98 * <li data-end="82" data-start="54"><code data-end="80" data-start="54">1 <= nums[i] <= 10^9
99 * <li data-end="120" data-start="85"><code data-end="118" data-start="85">1 <= queries.length <= 5 * 10^4
100 * <li data-end="195" data-start="123"><code data-end="193" data-is-only-node="" data-start="155">queries[i] = [li, ri, thresholdi]
101 * <li data-end="221" data-start="198"><code data-end="219" data-start="198">0 <= li <= ri < n
102 * <li data-end="259" data-is-last-node="" data-start="224"><code data-end="259" data-is-last-node="" data-start="224">1 <= thresholdi <= ri - li + 1
103 *
104 */
105pub struct Solution {}
106
107// problem: https://leetcode.com/problems/threshold-majority-queries/
108// discuss: https://leetcode.com/problems/threshold-majority-queries/discuss/?currentPage=1&orderBy=most_votes&query=
109
110// submission codes start here
111
112impl Solution {
113 pub fn subarray_majority(nums: Vec<i32>, queries: Vec<Vec<i32>>) -> Vec<i32> {
114 vec![]
115 }
116}
117
118// submission codes end
119
120#[cfg(test)]
121mod tests {
122 use super::*;
123
124 #[test]
125 fn test_3636() {
126 }
127}
128Back
© 2026 bowen.ge All Rights Reserved.