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 having length n and a 2D integer array queries where queries[i] = [idx, val].
For each query:
nums[idx] = val.k with 1 <= k < n to split the array into the non-empty prefix nums[0..k-1] and suffix nums[k..n-1] such that the sum of the counts of distinct prime values in each part is maximum.Note: The changes made to the array in one query persist into the next query.
Return an array containing the result for each query, in the order they are given.
Example 1:
Input: nums = [2,1,3,1,2], queries = [[1,2],[3,3]]
Output: [3,4]
Explanation:
nums = [2, 1, 3, 1, 2].nums = [2, 2, 3, 1, 2]. Split nums into [2] and [2, 3, 1, 2]. [2] consists of 1 distinct prime and [2, 3, 1, 2] consists of 2 distinct primes. Hence, the answer for this query is 1 + 2 = 3.nums = [2, 2, 3, 3, 2]. Split nums into [2, 2, 3] and [3, 2] with an answer of 2 + 2 = 4.[3, 4].Example 2:
Input: nums = [2,1,4], queries = [[0,1]]
Output: [0]
Explanation:
nums = [2, 1, 4].nums = [1, 1, 4]. There are no prime numbers in nums, hence the answer for this query is 0.[0].Constraints:
2 <= n == nums.length <= 5 * 1041 <= queries.length <= 5 * 1041 <= nums[i] <= 1050 <= queries[i][0] < nums.length1 <= queries[i][1] <= 105Problem summary: You are given an integer array nums having length n and a 2D integer array queries where queries[i] = [idx, val]. For each query: Update nums[idx] = val. Choose an integer k with 1 <= k < n to split the array into the non-empty prefix nums[0..k-1] and suffix nums[k..n-1] such that the sum of the counts of distinct prime values in each part is maximum. Note: The changes made to the array in one query persist into the next query. Return an array containing the result for each query, in the order they are given.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Array · Math · Segment Tree
[2,1,3,1,2] [[1,2],[3,3]]
[2,1,4] [[0,1]]
Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #3569: Maximize Count of Distinct Primes After Split
// Auto-generated Java example from go.
class Solution {
public void exampleSolution() {
}
}
// Reference (go):
// // Accepted solution for LeetCode #3569: Maximize Count of Distinct Primes After Split
// package main
//
// import (
// "github.com/emirpasic/gods/v2/trees/redblacktree"
// "math/bits"
// )
//
// // https://space.bilibili.com/206214
// const mx int = 1e5
//
// var np = [mx + 1]bool{true, true}
//
// func init() {
// for i := 2; i <= mx; i++ {
// if !np[i] {
// for j := i * i; j <= mx; j += i {
// np[j] = true
// }
// }
// }
// }
//
// type lazySeg []struct {
// l, r int
// mx int
// todo int
// }
//
// func mergeInfo(a, b int) int {
// return max(a, b)
// }
//
// const todoInit = 0
//
// func mergeTodo(f, old int) int {
// return f + old
// }
//
// func (t lazySeg) apply(o int, f int) {
// cur := &t[o]
// cur.mx += f
// cur.todo = mergeTodo(f, cur.todo)
// }
//
// func (t lazySeg) maintain(o int) {
// t[o].mx = mergeInfo(t[o<<1].mx, t[o<<1|1].mx)
// }
//
// func (t lazySeg) spread(o int) {
// f := t[o].todo
// if f == todoInit {
// return
// }
// t.apply(o<<1, f)
// t.apply(o<<1|1, f)
// t[o].todo = todoInit
// }
//
// func (t lazySeg) build(a []int, o, l, r int) {
// t[o].l, t[o].r = l, r
// t[o].todo = todoInit
// if l == r {
// t[o].mx = a[l]
// return
// }
// m := (l + r) >> 1
// t.build(a, o<<1, l, m)
// t.build(a, o<<1|1, m+1, r)
// t.maintain(o)
// }
//
// func (t lazySeg) update(o, l, r int, f int) {
// if l <= t[o].l && t[o].r <= r {
// t.apply(o, f)
// return
// }
// t.spread(o)
// m := (t[o].l + t[o].r) >> 1
// if l <= m {
// t.update(o<<1, l, r, f)
// }
// if m < r {
// t.update(o<<1|1, l, r, f)
// }
// t.maintain(o)
// }
//
// func (t lazySeg) query(o, l, r int) int {
// if l <= t[o].l && t[o].r <= r {
// return t[o].mx
// }
// t.spread(o)
// m := (t[o].l + t[o].r) >> 1
// if r <= m {
// return t.query(o<<1, l, r)
// }
// if l > m {
// return t.query(o<<1|1, l, r)
// }
// return mergeInfo(t.query(o<<1, l, r), t.query(o<<1|1, l, r))
// }
//
// func newLazySegmentTreeWithArray(a []int) lazySeg {
// n := len(a)
// t := make(lazySeg, 2<<bits.Len(uint(n-1)))
// t.build(a, 1, 0, n-1)
// return t
// }
//
// func newLazySegmentTree(n int, initVal int) lazySeg {
// a := make([]int, n)
// for i := range a {
// a[i] = initVal
// }
// return newLazySegmentTreeWithArray(a)
// }
//
// func maximumCount(nums []int, queries [][]int) (ans []int) {
// n := len(nums)
// pos := map[int]*redblacktree.Tree[int, struct{}]{}
// for i, x := range nums {
// if np[x] {
// continue
// }
// if _, ok := pos[x]; !ok {
// pos[x] = redblacktree.New[int, struct{}]()
// }
// pos[x].Put(i, struct{}{})
// }
//
// t := newLazySegmentTree(n, 0)
// for _, ps := range pos {
// if ps.Size() > 1 {
// t.update(1, ps.Left().Key, ps.Right().Key, 1)
// }
// }
//
// update := func(ps *redblacktree.Tree[int, struct{}], i, delta int) {
// l, r := ps.Left().Key, ps.Right().Key
// if l == r {
// t.update(1, min(l, i), max(r, i), delta)
// } else if i < l {
// t.update(1, i, l-1, delta)
// } else if i > r {
// t.update(1, r+1, i, delta)
// }
// }
//
// for _, q := range queries {
// i, v := q[0], q[1]
// old := nums[i]
// nums[i] = v
//
// if !np[old] {
// ps := pos[old]
// ps.Remove(i)
// if ps.Empty() {
// delete(pos, old)
// } else {
// update(ps, i, -1)
// }
// }
//
// if !np[v] {
// if ps, ok := pos[v]; !ok {
// pos[v] = redblacktree.New[int, struct{}]()
// } else {
// update(ps, i, 1)
// }
// pos[v].Put(i, struct{}{})
// }
//
// ans = append(ans, len(pos)+t.query(1, 0, n-1))
// }
// return
// }
// Accepted solution for LeetCode #3569: Maximize Count of Distinct Primes After Split
package main
import (
"github.com/emirpasic/gods/v2/trees/redblacktree"
"math/bits"
)
// https://space.bilibili.com/206214
const mx int = 1e5
var np = [mx + 1]bool{true, true}
func init() {
for i := 2; i <= mx; i++ {
if !np[i] {
for j := i * i; j <= mx; j += i {
np[j] = true
}
}
}
}
type lazySeg []struct {
l, r int
mx int
todo int
}
func mergeInfo(a, b int) int {
return max(a, b)
}
const todoInit = 0
func mergeTodo(f, old int) int {
return f + old
}
func (t lazySeg) apply(o int, f int) {
cur := &t[o]
cur.mx += f
cur.todo = mergeTodo(f, cur.todo)
}
func (t lazySeg) maintain(o int) {
t[o].mx = mergeInfo(t[o<<1].mx, t[o<<1|1].mx)
}
func (t lazySeg) spread(o int) {
f := t[o].todo
if f == todoInit {
return
}
t.apply(o<<1, f)
t.apply(o<<1|1, f)
t[o].todo = todoInit
}
func (t lazySeg) build(a []int, o, l, r int) {
t[o].l, t[o].r = l, r
t[o].todo = todoInit
if l == r {
t[o].mx = a[l]
return
}
m := (l + r) >> 1
t.build(a, o<<1, l, m)
t.build(a, o<<1|1, m+1, r)
t.maintain(o)
}
func (t lazySeg) update(o, l, r int, f int) {
if l <= t[o].l && t[o].r <= r {
t.apply(o, f)
return
}
t.spread(o)
m := (t[o].l + t[o].r) >> 1
if l <= m {
t.update(o<<1, l, r, f)
}
if m < r {
t.update(o<<1|1, l, r, f)
}
t.maintain(o)
}
func (t lazySeg) query(o, l, r int) int {
if l <= t[o].l && t[o].r <= r {
return t[o].mx
}
t.spread(o)
m := (t[o].l + t[o].r) >> 1
if r <= m {
return t.query(o<<1, l, r)
}
if l > m {
return t.query(o<<1|1, l, r)
}
return mergeInfo(t.query(o<<1, l, r), t.query(o<<1|1, l, r))
}
func newLazySegmentTreeWithArray(a []int) lazySeg {
n := len(a)
t := make(lazySeg, 2<<bits.Len(uint(n-1)))
t.build(a, 1, 0, n-1)
return t
}
func newLazySegmentTree(n int, initVal int) lazySeg {
a := make([]int, n)
for i := range a {
a[i] = initVal
}
return newLazySegmentTreeWithArray(a)
}
func maximumCount(nums []int, queries [][]int) (ans []int) {
n := len(nums)
pos := map[int]*redblacktree.Tree[int, struct{}]{}
for i, x := range nums {
if np[x] {
continue
}
if _, ok := pos[x]; !ok {
pos[x] = redblacktree.New[int, struct{}]()
}
pos[x].Put(i, struct{}{})
}
t := newLazySegmentTree(n, 0)
for _, ps := range pos {
if ps.Size() > 1 {
t.update(1, ps.Left().Key, ps.Right().Key, 1)
}
}
update := func(ps *redblacktree.Tree[int, struct{}], i, delta int) {
l, r := ps.Left().Key, ps.Right().Key
if l == r {
t.update(1, min(l, i), max(r, i), delta)
} else if i < l {
t.update(1, i, l-1, delta)
} else if i > r {
t.update(1, r+1, i, delta)
}
}
for _, q := range queries {
i, v := q[0], q[1]
old := nums[i]
nums[i] = v
if !np[old] {
ps := pos[old]
ps.Remove(i)
if ps.Empty() {
delete(pos, old)
} else {
update(ps, i, -1)
}
}
if !np[v] {
if ps, ok := pos[v]; !ok {
pos[v] = redblacktree.New[int, struct{}]()
} else {
update(ps, i, 1)
}
pos[v].Put(i, struct{}{})
}
ans = append(ans, len(pos)+t.query(1, 0, n-1))
}
return
}
# Accepted solution for LeetCode #3569: Maximize Count of Distinct Primes After Split
#
# @lc app=leetcode id=3569 lang=python3
#
# [3569] Maximize Count of Distinct Primes After Split
#
# @lc code=start
import heapq
class SegmentTree:
def __init__(self, n):
self.n = n
self.tree = [0] * (4 * n)
self.lazy = [0] * (4 * n)
def _push(self, node):
if self.lazy[node] != 0:
self.tree[2 * node] += self.lazy[node]
self.lazy[2 * node] += self.lazy[node]
self.tree[2 * node + 1] += self.lazy[node]
self.lazy[2 * node + 1] += self.lazy[node]
self.lazy[node] = 0
def update(self, node, start, end, l, r, val):
if l > end or r < start:
return
if l <= start and end <= r:
self.tree[node] += val
self.lazy[node] += val
return
self._push(node)
mid = (start + end) // 2
self.update(2 * node, start, mid, l, r, val)
self.update(2 * node + 1, mid + 1, end, l, r, val)
self.tree[node] = max(self.tree[2 * node], self.tree[2 * node + 1])
def query(self, node, start, end, l, r):
if l > end or r < start:
return 0
if l <= start and end <= r:
return self.tree[node]
self._push(node)
mid = (start + end) // 2
return max(self.query(2 * node, start, mid, l, r),
self.query(2 * node + 1, mid + 1, end, l, r))
# Precompute primes up to 10^5 + 5
MAX_VAL = 100005
is_prime = [True] * MAX_VAL
is_prime[0] = is_prime[1] = False
for i in range(2, int(MAX_VAL**0.5) + 1):
if is_prime[i]:
for j in range(i*i, MAX_VAL, i):
is_prime[j] = False
class Solution:
def maximumCount(self, nums: List[int], queries: List[List[int]]) -> List[int]:
n = len(nums)
st = SegmentTree(n)
# Structures to manage prime indices
# active_indices[p] = set of indices where p appears
# min_heap[p] = min heap of indices
# max_heap[p] = max heap of negative indices (to simulate max heap)
active_indices = {}
min_heap = {}
max_heap = {}
distinct_primes_count = 0
def get_range(p):
# Clean heaps
while min_heap[p] and min_heap[p][0] not in active_indices[p]:
heapq.heappop(min_heap[p])
while max_heap[p] and (-max_heap[p][0]) not in active_indices[p]:
heapq.heappop(max_heap[p])
if not min_heap[p]: return -1, -1
return min_heap[p][0], -max_heap[p][0]
def add_prime_idx(p, idx):
nonlocal distinct_primes_count
if p not in active_indices:
active_indices[p] = set()
min_heap[p] = []
max_heap[p] = []
distinct_primes_count += 1
if not active_indices[p]: # Was empty, now getting first element
active_indices[p].add(idx)
heapq.heappush(min_heap[p], idx)
heapq.heappush(max_heap[p], -idx)
# Range is [idx, idx], L < R is false, no tree update
return
# Already had elements. Remove old contribution.
l, r = get_range(p)
if l < r:
st.update(1, 0, n - 1, l + 1, r, -1)
active_indices[p].add(idx)
heapq.heappush(min_heap[p], idx)
heapq.heappush(max_heap[p], -idx)
# Add new contribution
l_new, r_new = get_range(p)
if l_new < r_new:
st.update(1, 0, n - 1, l_new + 1, r_new, 1)
def remove_prime_idx(p, idx):
nonlocal distinct_primes_count
# Assumes p is in active_indices and idx is in it
l, r = get_range(p)
if l < r:
st.update(1, 0, n - 1, l + 1, r, -1)
active_indices[p].remove(idx)
if not active_indices[p]:
distinct_primes_count -= 1
return
l_new, r_new = get_range(p)
if l_new < r_new:
st.update(1, 0, n - 1, l_new + 1, r_new, 1)
# Initial build
# Instead of calling add_prime_idx repeatedly which does tree updates,
# we can batch build. But N is small enough to just loop.
# Optimization: group indices first then update tree.
initial_indices = {}
for i, x in enumerate(nums):
if is_prime[x]:
if x not in initial_indices:
initial_indices[x] = []
initial_indices[x].append(i)
for p, idxs in initial_indices.items():
distinct_primes_count += 1
active_indices[p] = set(idxs)
min_heap[p] = list(idxs)
heapq.heapify(min_heap[p])
max_heap[p] = [-i for i in idxs]
heapq.heapify(max_heap[p])
l, r = idxs[0], idxs[-1]
if l < r:
st.update(1, 0, n - 1, l + 1, r, 1)
ans = []
for idx, val in queries:
old_val = nums[idx]
if old_val != val:
if is_prime[old_val]:
remove_prime_idx(old_val, idx)
nums[idx] = val
if is_prime[val]:
add_prime_idx(val, idx)
if distinct_primes_count == 0:
ans.append(0)
else:
# Query range [1, n-1]
mx_overlap = st.query(1, 0, n - 1, 1, n - 1)
ans.append(distinct_primes_count + mx_overlap)
return ans
# @lc code=end
// Accepted solution for LeetCode #3569: Maximize Count of Distinct Primes After Split
// 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 #3569: Maximize Count of Distinct Primes After Split
// package main
//
// import (
// "github.com/emirpasic/gods/v2/trees/redblacktree"
// "math/bits"
// )
//
// // https://space.bilibili.com/206214
// const mx int = 1e5
//
// var np = [mx + 1]bool{true, true}
//
// func init() {
// for i := 2; i <= mx; i++ {
// if !np[i] {
// for j := i * i; j <= mx; j += i {
// np[j] = true
// }
// }
// }
// }
//
// type lazySeg []struct {
// l, r int
// mx int
// todo int
// }
//
// func mergeInfo(a, b int) int {
// return max(a, b)
// }
//
// const todoInit = 0
//
// func mergeTodo(f, old int) int {
// return f + old
// }
//
// func (t lazySeg) apply(o int, f int) {
// cur := &t[o]
// cur.mx += f
// cur.todo = mergeTodo(f, cur.todo)
// }
//
// func (t lazySeg) maintain(o int) {
// t[o].mx = mergeInfo(t[o<<1].mx, t[o<<1|1].mx)
// }
//
// func (t lazySeg) spread(o int) {
// f := t[o].todo
// if f == todoInit {
// return
// }
// t.apply(o<<1, f)
// t.apply(o<<1|1, f)
// t[o].todo = todoInit
// }
//
// func (t lazySeg) build(a []int, o, l, r int) {
// t[o].l, t[o].r = l, r
// t[o].todo = todoInit
// if l == r {
// t[o].mx = a[l]
// return
// }
// m := (l + r) >> 1
// t.build(a, o<<1, l, m)
// t.build(a, o<<1|1, m+1, r)
// t.maintain(o)
// }
//
// func (t lazySeg) update(o, l, r int, f int) {
// if l <= t[o].l && t[o].r <= r {
// t.apply(o, f)
// return
// }
// t.spread(o)
// m := (t[o].l + t[o].r) >> 1
// if l <= m {
// t.update(o<<1, l, r, f)
// }
// if m < r {
// t.update(o<<1|1, l, r, f)
// }
// t.maintain(o)
// }
//
// func (t lazySeg) query(o, l, r int) int {
// if l <= t[o].l && t[o].r <= r {
// return t[o].mx
// }
// t.spread(o)
// m := (t[o].l + t[o].r) >> 1
// if r <= m {
// return t.query(o<<1, l, r)
// }
// if l > m {
// return t.query(o<<1|1, l, r)
// }
// return mergeInfo(t.query(o<<1, l, r), t.query(o<<1|1, l, r))
// }
//
// func newLazySegmentTreeWithArray(a []int) lazySeg {
// n := len(a)
// t := make(lazySeg, 2<<bits.Len(uint(n-1)))
// t.build(a, 1, 0, n-1)
// return t
// }
//
// func newLazySegmentTree(n int, initVal int) lazySeg {
// a := make([]int, n)
// for i := range a {
// a[i] = initVal
// }
// return newLazySegmentTreeWithArray(a)
// }
//
// func maximumCount(nums []int, queries [][]int) (ans []int) {
// n := len(nums)
// pos := map[int]*redblacktree.Tree[int, struct{}]{}
// for i, x := range nums {
// if np[x] {
// continue
// }
// if _, ok := pos[x]; !ok {
// pos[x] = redblacktree.New[int, struct{}]()
// }
// pos[x].Put(i, struct{}{})
// }
//
// t := newLazySegmentTree(n, 0)
// for _, ps := range pos {
// if ps.Size() > 1 {
// t.update(1, ps.Left().Key, ps.Right().Key, 1)
// }
// }
//
// update := func(ps *redblacktree.Tree[int, struct{}], i, delta int) {
// l, r := ps.Left().Key, ps.Right().Key
// if l == r {
// t.update(1, min(l, i), max(r, i), delta)
// } else if i < l {
// t.update(1, i, l-1, delta)
// } else if i > r {
// t.update(1, r+1, i, delta)
// }
// }
//
// for _, q := range queries {
// i, v := q[0], q[1]
// old := nums[i]
// nums[i] = v
//
// if !np[old] {
// ps := pos[old]
// ps.Remove(i)
// if ps.Empty() {
// delete(pos, old)
// } else {
// update(ps, i, -1)
// }
// }
//
// if !np[v] {
// if ps, ok := pos[v]; !ok {
// pos[v] = redblacktree.New[int, struct{}]()
// } else {
// update(ps, i, 1)
// }
// pos[v].Put(i, struct{}{})
// }
//
// ans = append(ans, len(pos)+t.query(1, 0, n-1))
// }
// return
// }
// Accepted solution for LeetCode #3569: Maximize Count of Distinct Primes After Split
// Auto-generated TypeScript example from go.
function exampleSolution(): void {
}
// Reference (go):
// // Accepted solution for LeetCode #3569: Maximize Count of Distinct Primes After Split
// package main
//
// import (
// "github.com/emirpasic/gods/v2/trees/redblacktree"
// "math/bits"
// )
//
// // https://space.bilibili.com/206214
// const mx int = 1e5
//
// var np = [mx + 1]bool{true, true}
//
// func init() {
// for i := 2; i <= mx; i++ {
// if !np[i] {
// for j := i * i; j <= mx; j += i {
// np[j] = true
// }
// }
// }
// }
//
// type lazySeg []struct {
// l, r int
// mx int
// todo int
// }
//
// func mergeInfo(a, b int) int {
// return max(a, b)
// }
//
// const todoInit = 0
//
// func mergeTodo(f, old int) int {
// return f + old
// }
//
// func (t lazySeg) apply(o int, f int) {
// cur := &t[o]
// cur.mx += f
// cur.todo = mergeTodo(f, cur.todo)
// }
//
// func (t lazySeg) maintain(o int) {
// t[o].mx = mergeInfo(t[o<<1].mx, t[o<<1|1].mx)
// }
//
// func (t lazySeg) spread(o int) {
// f := t[o].todo
// if f == todoInit {
// return
// }
// t.apply(o<<1, f)
// t.apply(o<<1|1, f)
// t[o].todo = todoInit
// }
//
// func (t lazySeg) build(a []int, o, l, r int) {
// t[o].l, t[o].r = l, r
// t[o].todo = todoInit
// if l == r {
// t[o].mx = a[l]
// return
// }
// m := (l + r) >> 1
// t.build(a, o<<1, l, m)
// t.build(a, o<<1|1, m+1, r)
// t.maintain(o)
// }
//
// func (t lazySeg) update(o, l, r int, f int) {
// if l <= t[o].l && t[o].r <= r {
// t.apply(o, f)
// return
// }
// t.spread(o)
// m := (t[o].l + t[o].r) >> 1
// if l <= m {
// t.update(o<<1, l, r, f)
// }
// if m < r {
// t.update(o<<1|1, l, r, f)
// }
// t.maintain(o)
// }
//
// func (t lazySeg) query(o, l, r int) int {
// if l <= t[o].l && t[o].r <= r {
// return t[o].mx
// }
// t.spread(o)
// m := (t[o].l + t[o].r) >> 1
// if r <= m {
// return t.query(o<<1, l, r)
// }
// if l > m {
// return t.query(o<<1|1, l, r)
// }
// return mergeInfo(t.query(o<<1, l, r), t.query(o<<1|1, l, r))
// }
//
// func newLazySegmentTreeWithArray(a []int) lazySeg {
// n := len(a)
// t := make(lazySeg, 2<<bits.Len(uint(n-1)))
// t.build(a, 1, 0, n-1)
// return t
// }
//
// func newLazySegmentTree(n int, initVal int) lazySeg {
// a := make([]int, n)
// for i := range a {
// a[i] = initVal
// }
// return newLazySegmentTreeWithArray(a)
// }
//
// func maximumCount(nums []int, queries [][]int) (ans []int) {
// n := len(nums)
// pos := map[int]*redblacktree.Tree[int, struct{}]{}
// for i, x := range nums {
// if np[x] {
// continue
// }
// if _, ok := pos[x]; !ok {
// pos[x] = redblacktree.New[int, struct{}]()
// }
// pos[x].Put(i, struct{}{})
// }
//
// t := newLazySegmentTree(n, 0)
// for _, ps := range pos {
// if ps.Size() > 1 {
// t.update(1, ps.Left().Key, ps.Right().Key, 1)
// }
// }
//
// update := func(ps *redblacktree.Tree[int, struct{}], i, delta int) {
// l, r := ps.Left().Key, ps.Right().Key
// if l == r {
// t.update(1, min(l, i), max(r, i), delta)
// } else if i < l {
// t.update(1, i, l-1, delta)
// } else if i > r {
// t.update(1, r+1, i, delta)
// }
// }
//
// for _, q := range queries {
// i, v := q[0], q[1]
// old := nums[i]
// nums[i] = v
//
// if !np[old] {
// ps := pos[old]
// ps.Remove(i)
// if ps.Empty() {
// delete(pos, old)
// } else {
// update(ps, i, -1)
// }
// }
//
// if !np[v] {
// if ps, ok := pos[v]; !ok {
// pos[v] = redblacktree.New[int, struct{}]()
// } else {
// update(ps, i, 1)
// }
// pos[v].Put(i, struct{}{})
// }
//
// ans = append(ans, len(pos)+t.query(1, 0, n-1))
// }
// return
// }
Use this to step through a reusable interview workflow for this problem.
For each of q queries, scan the entire range to compute the aggregate (sum, min, max). Each range scan takes up to O(n) for a full-array query. With q queries: O(n × q) total. Point updates are O(1) but queries dominate.
Building the tree is O(n). Each query or update traverses O(log n) nodes (tree height). For q queries: O(n + q log n) total. Space is O(4n) ≈ O(n) for the tree array. Lazy propagation adds O(1) per node for deferred updates.
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: Temporary multiplications exceed integer bounds.
Usually fails on: Large inputs wrap around unexpectedly.
Fix: Use wider types, modular arithmetic, or rearranged operations.