Off-by-one on range boundaries
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Break down a hard problem into reliable checkpoints, edge-case handling, and complexity trade-offs.
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 + 1Problem summary: 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.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Array · Hash Map · Binary Search
[1,1,2,2,1,1] [[0,5,4],[0,3,3],[2,3,2]]
[3,2,3,2,3,2,3] [[0,6,4],[1,5,2],[2,4,1],[3,3,1]]
Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #3636: Threshold Majority Queries
// Auto-generated Java example from go.
class Solution {
public void exampleSolution() {
}
}
// Reference (go):
// // Accepted solution for LeetCode #3636: Threshold Majority Queries
// package main
//
// import (
// "cmp"
// "math"
// "slices"
// "sort"
// )
//
// // https://space.bilibili.com/206214
// func subarrayMajority(nums []int, queries [][]int) []int {
// n, m := len(nums), len(queries)
//
// a := slices.Clone(nums)
// slices.Sort(a)
// a = slices.Compact(a)
// indexToValue := make([]int, n)
// for i, x := range nums {
// indexToValue[i] = sort.SearchInts(a, x)
// }
//
// cnt := make([]int, len(a)+1)
// maxCnt, minVal := 0, 0
// add := func(i int) {
// v := indexToValue[i]
// cnt[v]++
// c := cnt[v]
// x := nums[i]
// if c > maxCnt {
// maxCnt, minVal = c, x
// } else if c == maxCnt {
// minVal = min(minVal, x)
// }
// }
//
// ans := make([]int, m)
// blockSize := int(math.Ceil(float64(n) / math.Sqrt(float64(m*2))))
// type query struct{ bid, l, r, threshold, qid int } // [l,r) 左闭右开
// qs := []query{}
// for i, q := range queries {
// l, r, threshold := q[0], q[1]+1, q[2] // 左闭右开
// // 大区间离线（保证 l 和 r 不在同一个块中）
// if r-l > blockSize {
// qs = append(qs, query{l / blockSize, l, r, threshold, i})
// continue
// }
// // 小区间暴力
// for j := l; j < r; j++ {
// add(j)
// }
// if maxCnt >= threshold {
// ans[i] = minVal
// } else {
// ans[i] = -1
// }
// // 重置数据
// for _, v := range indexToValue[l:r] {
// cnt[v]--
// }
// maxCnt = 0
// }
//
// slices.SortFunc(qs, func(a, b query) int { return cmp.Or(a.bid-b.bid, a.r-b.r) })
//
// var r int
// for i, q := range qs {
// l0 := (q.bid + 1) * blockSize
// if i == 0 || q.bid > qs[i-1].bid { // 遍历到一个新的块
// r = l0 // 右端点移动的起点
// // 重置数据
// clear(cnt)
// maxCnt = 0
// }
//
// // 右端点从 r 移动到 q.r（q.r 不计入）
// for ; r < q.r; r++ {
// add(r)
// }
//
// // 左端点从 l0 移动到 q.l（l0 不计入）
// tmpMaxCnt, tmpMinVal := maxCnt, minVal
// for l := q.l; l < l0; l++ {
// add(l)
// }
// if maxCnt >= q.threshold {
// ans[q.qid] = minVal
// } else {
// ans[q.qid] = -1
// }
//
// // 回滚
// maxCnt, minVal = tmpMaxCnt, tmpMinVal
// for _, v := range indexToValue[q.l:l0] {
// cnt[v]--
// }
// }
// return ans
// }
// Accepted solution for LeetCode #3636: Threshold Majority Queries
package main
import (
"cmp"
"math"
"slices"
"sort"
)
// https://space.bilibili.com/206214
func subarrayMajority(nums []int, queries [][]int) []int {
n, m := len(nums), len(queries)
a := slices.Clone(nums)
slices.Sort(a)
a = slices.Compact(a)
indexToValue := make([]int, n)
for i, x := range nums {
indexToValue[i] = sort.SearchInts(a, x)
}
cnt := make([]int, len(a)+1)
maxCnt, minVal := 0, 0
add := func(i int) {
v := indexToValue[i]
cnt[v]++
c := cnt[v]
x := nums[i]
if c > maxCnt {
maxCnt, minVal = c, x
} else if c == maxCnt {
minVal = min(minVal, x)
}
}
ans := make([]int, m)
blockSize := int(math.Ceil(float64(n) / math.Sqrt(float64(m*2))))
type query struct{ bid, l, r, threshold, qid int } // [l,r) 左闭右开
qs := []query{}
for i, q := range queries {
l, r, threshold := q[0], q[1]+1, q[2] // 左闭右开
// 大区间离线（保证 l 和 r 不在同一个块中）
if r-l > blockSize {
qs = append(qs, query{l / blockSize, l, r, threshold, i})
continue
}
// 小区间暴力
for j := l; j < r; j++ {
add(j)
}
if maxCnt >= threshold {
ans[i] = minVal
} else {
ans[i] = -1
}
// 重置数据
for _, v := range indexToValue[l:r] {
cnt[v]--
}
maxCnt = 0
}
slices.SortFunc(qs, func(a, b query) int { return cmp.Or(a.bid-b.bid, a.r-b.r) })
var r int
for i, q := range qs {
l0 := (q.bid + 1) * blockSize
if i == 0 || q.bid > qs[i-1].bid { // 遍历到一个新的块
r = l0 // 右端点移动的起点
// 重置数据
clear(cnt)
maxCnt = 0
}
// 右端点从 r 移动到 q.r（q.r 不计入）
for ; r < q.r; r++ {
add(r)
}
// 左端点从 l0 移动到 q.l（l0 不计入）
tmpMaxCnt, tmpMinVal := maxCnt, minVal
for l := q.l; l < l0; l++ {
add(l)
}
if maxCnt >= q.threshold {
ans[q.qid] = minVal
} else {
ans[q.qid] = -1
}
// 回滚
maxCnt, minVal = tmpMaxCnt, tmpMinVal
for _, v := range indexToValue[q.l:l0] {
cnt[v]--
}
}
return ans
}
# Accepted solution for LeetCode #3636: Threshold Majority Queries
# Time: O(nlogn + qlogq + (n + q) * sqrt(n) + q * n)
# Space: O(n + q)
# sort, coordinate compression, mo's algorithm
class Solution(object):
def subarrayMajority(self, nums, queries):
"""
:type nums: List[int]
:type queries: List[List[int]]
:rtype: List[int]
"""
# reference: https://cp-algorithms.com/data_structures/sqrt_decomposition.html
def mo_s_algorithm(): # Time: O(QlogQ + (N + Q) * sqrt(N) + Q * N)
def add(i): # Time: O(F) = O(1)
idx = num_to_idx[nums[i]]
if cnt[idx]:
cnt2[cnt[idx]] -= 1
cnt[idx] += 1
cnt2[cnt[idx]] += 1
max_freq[0] = max(max_freq[0], cnt[idx])
def remove(i): # Time: O(F) = O(1)
idx = num_to_idx[nums[i]]
cnt2[cnt[idx]] -= 1
if not cnt2[max_freq[0]]:
max_freq[0] -= 1
cnt[idx] -= 1
if cnt[idx]:
cnt2[cnt[idx]] += 1
def get_ans(t): # Time: O(A) = O(N)
if max_freq[0] < t:
return -1
i = next(i for i in xrange(len(cnt)) if cnt[i] == max_freq[0])
return sorted_nums[i]
cnt = [0]*len(num_to_idx)
cnt2 = [0]*(len(nums)+1)
max_freq = [0]
result = [-1]*len(queries)
block_size = int(len(nums)**0.5)+1 # O(S) = O(sqrt(N))
idxs = range(len(queries))
idxs.sort(key=lambda x: (queries[x][0]//block_size, queries[x][1] if (queries[x][0]//block_size)&1 else -queries[x][1])) # Time: O(QlogQ)
left, right = 0, -1
for i in idxs: # Time: O((N / S) * N * F + S * Q * F + Q * A) = O((N + Q) * sqrt(N) + Q * N), O(S) = O(sqrt(N)), O(F) = O(logN), O(A) = O(1)
l, r, t = queries[i]
while left > l:
left -= 1
add(left)
while right < r:
right += 1
add(right)
while left < l:
remove(left)
left += 1
while right > r:
remove(right)
right -= 1
result[i] = get_ans(t)
return result
sorted_nums = sorted(set(nums))
num_to_idx = {x:i for i, x in enumerate(sorted_nums)}
return mo_s_algorithm()
# Time: O(nlogn + qlogq + (n + q) * sqrt(n) * logn)
# Space: O(n + q)
from sortedcontainers import SortedList
# sort, coordinate compression, mo's algorithm, sorted list
class Solution_TLE(object):
def subarrayMajority(self, nums, queries):
"""
:type nums: List[int]
:type queries: List[List[int]]
:rtype: List[int]
"""
# reference: https://cp-algorithms.com/data_structures/sqrt_decomposition.html
def mo_s_algorithm(): # Time: O(QlogQ + (N + Q) * sqrt(N) * logN)
def add(i): # Time: O(F) = O(logN)
idx = num_to_idx[nums[i]]
if cnt[idx]:
lookup[cnt[idx]].remove(nums[i])
cnt[idx] += 1
lookup[cnt[idx]].add(nums[i])
max_freq[0] = max(max_freq[0], cnt[idx])
def remove(i): # Time: O(F) = O(logN)
idx = num_to_idx[nums[i]]
lookup[cnt[idx]].remove(nums[i])
if not lookup[max_freq[0]]:
max_freq[0] -= 1
cnt[idx] -= 1
if cnt[idx]:
lookup[cnt[idx]].add(nums[i])
def get_ans(t): # Time: O(A) = O(logN)
return lookup[max_freq[0]][0] if max_freq[0] >= t else -1
cnt = [0]*len(num_to_idx)
lookup = [SortedList() for _ in xrange(len(nums)+1)]
max_freq = [0]
result = [-1]*len(queries)
block_size = int(len(nums)**0.5)+1 # O(S) = O(sqrt(N))
idxs = range(len(queries))
idxs.sort(key=lambda x: (queries[x][0]//block_size, queries[x][1] if (queries[x][0]//block_size)&1 else -queries[x][1])) # Time: O(QlogQ)
left, right = 0, -1
for i in idxs: # Time: O((N / S) * N * F + S * Q * F + Q * A) = O((N + Q) * sqrt(N) * logN), O(S) = O(sqrt(N)), O(F) = O(logN), O(A) = O(1)
l, r, t = queries[i]
while left > l:
left -= 1
add(left)
while right < r:
right += 1
add(right)
while left < l:
remove(left)
left += 1
while right > r:
remove(right)
right -= 1
result[i] = get_ans(t)
return result
num_to_idx = {x:i for i, x in enumerate(sorted(set(nums)))}
return mo_s_algorithm()
// Accepted solution for LeetCode #3636: Threshold Majority Queries
// Rust example auto-generated from go reference.
// Replace the signature and local types with the exact LeetCode harness for this problem.
impl Solution {
pub fn rust_example() {
// Port the logic from the reference block below.
}
}
// Reference (go):
// // Accepted solution for LeetCode #3636: Threshold Majority Queries
// package main
//
// import (
// "cmp"
// "math"
// "slices"
// "sort"
// )
//
// // https://space.bilibili.com/206214
// func subarrayMajority(nums []int, queries [][]int) []int {
// n, m := len(nums), len(queries)
//
// a := slices.Clone(nums)
// slices.Sort(a)
// a = slices.Compact(a)
// indexToValue := make([]int, n)
// for i, x := range nums {
// indexToValue[i] = sort.SearchInts(a, x)
// }
//
// cnt := make([]int, len(a)+1)
// maxCnt, minVal := 0, 0
// add := func(i int) {
// v := indexToValue[i]
// cnt[v]++
// c := cnt[v]
// x := nums[i]
// if c > maxCnt {
// maxCnt, minVal = c, x
// } else if c == maxCnt {
// minVal = min(minVal, x)
// }
// }
//
// ans := make([]int, m)
// blockSize := int(math.Ceil(float64(n) / math.Sqrt(float64(m*2))))
// type query struct{ bid, l, r, threshold, qid int } // [l,r) 左闭右开
// qs := []query{}
// for i, q := range queries {
// l, r, threshold := q[0], q[1]+1, q[2] // 左闭右开
// // 大区间离线（保证 l 和 r 不在同一个块中）
// if r-l > blockSize {
// qs = append(qs, query{l / blockSize, l, r, threshold, i})
// continue
// }
// // 小区间暴力
// for j := l; j < r; j++ {
// add(j)
// }
// if maxCnt >= threshold {
// ans[i] = minVal
// } else {
// ans[i] = -1
// }
// // 重置数据
// for _, v := range indexToValue[l:r] {
// cnt[v]--
// }
// maxCnt = 0
// }
//
// slices.SortFunc(qs, func(a, b query) int { return cmp.Or(a.bid-b.bid, a.r-b.r) })
//
// var r int
// for i, q := range qs {
// l0 := (q.bid + 1) * blockSize
// if i == 0 || q.bid > qs[i-1].bid { // 遍历到一个新的块
// r = l0 // 右端点移动的起点
// // 重置数据
// clear(cnt)
// maxCnt = 0
// }
//
// // 右端点从 r 移动到 q.r（q.r 不计入）
// for ; r < q.r; r++ {
// add(r)
// }
//
// // 左端点从 l0 移动到 q.l（l0 不计入）
// tmpMaxCnt, tmpMinVal := maxCnt, minVal
// for l := q.l; l < l0; l++ {
// add(l)
// }
// if maxCnt >= q.threshold {
// ans[q.qid] = minVal
// } else {
// ans[q.qid] = -1
// }
//
// // 回滚
// maxCnt, minVal = tmpMaxCnt, tmpMinVal
// for _, v := range indexToValue[q.l:l0] {
// cnt[v]--
// }
// }
// return ans
// }
// Accepted solution for LeetCode #3636: Threshold Majority Queries
// Auto-generated TypeScript example from go.
function exampleSolution(): void {
}
// Reference (go):
// // Accepted solution for LeetCode #3636: Threshold Majority Queries
// package main
//
// import (
// "cmp"
// "math"
// "slices"
// "sort"
// )
//
// // https://space.bilibili.com/206214
// func subarrayMajority(nums []int, queries [][]int) []int {
// n, m := len(nums), len(queries)
//
// a := slices.Clone(nums)
// slices.Sort(a)
// a = slices.Compact(a)
// indexToValue := make([]int, n)
// for i, x := range nums {
// indexToValue[i] = sort.SearchInts(a, x)
// }
//
// cnt := make([]int, len(a)+1)
// maxCnt, minVal := 0, 0
// add := func(i int) {
// v := indexToValue[i]
// cnt[v]++
// c := cnt[v]
// x := nums[i]
// if c > maxCnt {
// maxCnt, minVal = c, x
// } else if c == maxCnt {
// minVal = min(minVal, x)
// }
// }
//
// ans := make([]int, m)
// blockSize := int(math.Ceil(float64(n) / math.Sqrt(float64(m*2))))
// type query struct{ bid, l, r, threshold, qid int } // [l,r) 左闭右开
// qs := []query{}
// for i, q := range queries {
// l, r, threshold := q[0], q[1]+1, q[2] // 左闭右开
// // 大区间离线（保证 l 和 r 不在同一个块中）
// if r-l > blockSize {
// qs = append(qs, query{l / blockSize, l, r, threshold, i})
// continue
// }
// // 小区间暴力
// for j := l; j < r; j++ {
// add(j)
// }
// if maxCnt >= threshold {
// ans[i] = minVal
// } else {
// ans[i] = -1
// }
// // 重置数据
// for _, v := range indexToValue[l:r] {
// cnt[v]--
// }
// maxCnt = 0
// }
//
// slices.SortFunc(qs, func(a, b query) int { return cmp.Or(a.bid-b.bid, a.r-b.r) })
//
// var r int
// for i, q := range qs {
// l0 := (q.bid + 1) * blockSize
// if i == 0 || q.bid > qs[i-1].bid { // 遍历到一个新的块
// r = l0 // 右端点移动的起点
// // 重置数据
// clear(cnt)
// maxCnt = 0
// }
//
// // 右端点从 r 移动到 q.r（q.r 不计入）
// for ; r < q.r; r++ {
// add(r)
// }
//
// // 左端点从 l0 移动到 q.l（l0 不计入）
// tmpMaxCnt, tmpMinVal := maxCnt, minVal
// for l := q.l; l < l0; l++ {
// add(l)
// }
// if maxCnt >= q.threshold {
// ans[q.qid] = minVal
// } else {
// ans[q.qid] = -1
// }
//
// // 回滚
// maxCnt, minVal = tmpMaxCnt, tmpMinVal
// for _, v := range indexToValue[q.l:l0] {
// cnt[v]--
// }
// }
// return ans
// }
Use this to step through a reusable interview workflow for this problem.
Check every element from left to right until we find the target or exhaust the array. Each comparison is O(1), and we may visit all n elements, giving O(n). No extra space needed.
Each comparison eliminates half the remaining search space. After k comparisons, the space is n/2ᵏ. We stop when the space is 1, so k = log₂ n. No extra memory needed — just two pointers (lo, hi).
Review these before coding to avoid predictable interview regressions.
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Wrong move: Zero-count keys stay in map and break distinct/count constraints.
Usually fails on: Window/map size checks are consistently off by one.
Fix: Delete keys when count reaches zero.
Wrong move: Setting `lo = mid` or `hi = mid` can stall and create an infinite loop.
Usually fails on: Two-element ranges never converge.
Fix: Use `lo = mid + 1` or `hi = mid - 1` where appropriate.