# 22.05.2025 [3362. Zero Array Transformation III]
Max removed queries still zero-fy an array #medium #heap
22.05.2025
3362. Zero Array Transformation III medium blog post substack youtube
Join me on Telegram
Problem TLDR
Max removed queries still zero-fy an array #medium #heap
Intuition
Didn't solved.
Irrelevant chain-of-thougths for history:
// [1,1,1,1]
// [[1,3],[0,2],[1,3],[1,2]]
// 0,2 1,2 1,3 1,3
// 0 1 2 3
// 0, 3, 3, 1, -2
// i j 0,2 take
// 1,2 drop, 3,3 -> 2,2 min=2
// i j 1,3 drop, 2,2,1 -> 2,2,0, min=0
// *running interval minimum* increasing queue?
// looks like too hard for medium, maybe wrong algo?
// use hints
// sort: already done
// pick max end: already do ?
//
// [1,1,1,1]
// i 1..3
// i max = 1
// 1..3
// 2 0 2
// 1 1 0..2
//
// 2 2 0..2
// 1 1..1 move and compute running sum
// ok, i fail
The working solution:
sort queries by start
iterate the nums
maintain the current accepted queries sum
put accepted queries (start, end) into a line sweep diff array
hard part: put candidate queries (same start) ends into a sorted heap, poll lazily when needed
Approach
it looks like I've solved it previously in contest, but havn't absorbed the solution, or, even possible degraded in the solution search
I've solved the wrong problem on the start and spent some mind power
Complexity
Time complexity: $$O(nlog(n))$$
Space complexity: $$O(n)$$
Code
fun maxRemoval(nums: IntArray, queries: Array<IntArray>): Int {
val h = PriorityQueue<Int>(); val d = IntArray(nums.size + 1)
queries.sortBy { it[0] }; var qsum = 0; var j = 0
for ((i, x) in nums.withIndex()) {
while (j < queries.size && queries[j][0] == i) h += -queries[j++][1]
qsum += d[i]
while (x > qsum && h.size > 0 && -h.peek() >= i) {
d[-h.poll() + 1]--; qsum++
}
if (x > qsum) return -1
}
return h.size
}
pub fn max_removal(n: Vec<i32>, mut q: Vec<Vec<i32>>) -> i32 {
let (mut h, mut d) = (BinaryHeap::new(), vec![0; n.len() + 1]);
q.sort_unstable(); let (mut lvl, mut j) = (0, 0);
for i in 0..n.len() {
while j < q.len() && q[j][0] == i as i32 { h.push(q[j][1] as usize); j += 1 }
lvl += d[i];
while n[i] > lvl && h.len() > 0 && *h.peek().unwrap() >= i {
d[h.pop().unwrap() + 1] -= 1; lvl += 1
}
if n[i] > lvl { return -1 }
} h.len() as _
}
int maxRemoval(vector<int>& n, vector<vector<int>>& q) {
priority_queue<int> h; int l = 0, j = 0;
vector<int> d(n.size() + 1); sort(q.begin(), q.end());
for (int i = 0, N = n.size(); i < N; ++i) {
while (j < q.size() && q[j][0] == i)
h.push(q[j++][1]);
l += d[i];
while (l < n[i] && !h.empty() && h.top() >= i)
l++, d[h.top() + 1]--, h.pop();
if (l < n[i]) return -1;
}
return h.size();
}