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.
Move from brute-force thinking to an efficient approach using array strategy.
You are given an integer array nums of length n and a 2D array queries where queries[i] = [li, ri].
Each queries[i] represents the following action on nums:
[li, ri] in nums by at most 1.A Zero Array is an array with all its elements equal to 0.
Return the maximum number of elements that can be removed from queries, such that nums can still be converted to a zero array using the remaining queries. If it is not possible to convert nums to a zero array, return -1.
Example 1:
Input: nums = [2,0,2], queries = [[0,2],[0,2],[1,1]]
Output: 1
Explanation:
After removing queries[2], nums can still be converted to a zero array.
queries[0], decrement nums[0] and nums[2] by 1 and nums[1] by 0.queries[1], decrement nums[0] and nums[2] by 1 and nums[1] by 0.Example 2:
Input: nums = [1,1,1,1], queries = [[1,3],[0,2],[1,3],[1,2]]
Output: 2
Explanation:
We can remove queries[2] and queries[3].
Example 3:
Input: nums = [1,2,3,4], queries = [[0,3]]
Output: -1
Explanation:
nums cannot be converted to a zero array even after using all the queries.
Constraints:
1 <= nums.length <= 1050 <= nums[i] <= 1051 <= queries.length <= 105queries[i].length == 20 <= li <= ri < nums.lengthProblem summary: You are given an integer array nums of length n and a 2D array queries where queries[i] = [li, ri]. Each queries[i] represents the following action on nums: Decrement the value at each index in the range [li, ri] in nums by at most 1. The amount by which the value is decremented can be chosen independently for each index. A Zero Array is an array with all its elements equal to 0. Return the maximum number of elements that can be removed from queries, such that nums can still be converted to a zero array using the remaining queries. If it is not possible to convert nums to a zero array, return -1.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Array · Greedy
[2,0,2] [[0,2],[0,2],[1,1]]
[1,1,1,1] [[1,3],[0,2],[1,3],[1,2]]
[1,2,3,4] [[0,3]]
corporate-flight-bookings)minimum-moves-to-make-array-complementary)zero-array-transformation-iv)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #3362: Zero Array Transformation III
class Solution {
public int maxRemoval(int[] nums, int[][] queries) {
Arrays.sort(queries, (a, b) -> Integer.compare(a[0], b[0]));
PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);
int n = nums.length;
int[] d = new int[n + 1];
int s = 0, j = 0;
for (int i = 0; i < n; i++) {
s += d[i];
while (j < queries.length && queries[j][0] <= i) {
pq.offer(queries[j][1]);
j++;
}
while (s < nums[i] && !pq.isEmpty() && pq.peek() >= i) {
s++;
d[pq.poll() + 1]--;
}
if (s < nums[i]) {
return -1;
}
}
return pq.size();
}
}
// Accepted solution for LeetCode #3362: Zero Array Transformation III
func maxRemoval(nums []int, queries [][]int) int {
sort.Slice(queries, func(i, j int) bool {
return queries[i][0] < queries[j][0]
})
var h hp
heap.Init(&h)
n := len(nums)
d := make([]int, n+1)
s, j := 0, 0
for i := 0; i < n; i++ {
s += d[i]
for j < len(queries) && queries[j][0] <= i {
heap.Push(&h, queries[j][1])
j++
}
for s < nums[i] && h.Len() > 0 && h.IntSlice[0] >= i {
s++
end := heap.Pop(&h).(int)
if end+1 < len(d) {
d[end+1]--
}
}
if s < nums[i] {
return -1
}
}
return h.Len()
}
type hp struct{ sort.IntSlice }
func (h hp) Less(i, j int) bool { return h.IntSlice[i] > h.IntSlice[j] }
func (h *hp) Push(v any) { h.IntSlice = append(h.IntSlice, v.(int)) }
func (h *hp) Pop() any {
a := h.IntSlice
v := a[len(a)-1]
h.IntSlice = a[:len(a)-1]
return v
}
# Accepted solution for LeetCode #3362: Zero Array Transformation III
class Solution:
def maxRemoval(self, nums: List[int], queries: List[List[int]]) -> int:
queries.sort()
pq = []
d = [0] * (len(nums) + 1)
s = j = 0
for i, x in enumerate(nums):
s += d[i]
while j < len(queries) and queries[j][0] <= i:
heappush(pq, -queries[j][1])
j += 1
while s < x and pq and -pq[0] >= i:
s += 1
d[-heappop(pq) + 1] -= 1
if s < x:
return -1
return len(pq)
// Accepted solution for LeetCode #3362: Zero Array Transformation III
/**
* [3362] Zero Array Transformation III
*/
pub struct Solution {}
// submission codes start here
use std::collections::BinaryHeap;
impl Solution {
pub fn max_removal(nums: Vec<i32>, mut queries: Vec<Vec<i32>>) -> i32 {
queries.sort_unstable_by(|a, b| a[0].cmp(&b[0]));
let mut heap = BinaryHeap::new();
let mut difference_array = vec![0; nums.len() + 1];
let mut prefix_sum = 0;
let mut pos = 0;
for i in 0..nums.len() {
prefix_sum += difference_array[i];
while pos < queries.len() && queries[pos][0] as usize == i {
heap.push(queries[pos][1] as usize);
pos += 1;
}
while prefix_sum < nums[i] {
if let Some(&right) = heap.peek() {
if right >= i {
prefix_sum += 1;
difference_array[right + 1] -= 1;
heap.pop();
} else {
break;
}
} else {
break;
}
}
if prefix_sum < nums[i] {
return -1;
}
}
heap.len() as i32
}
}
// submission codes end
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_3362() {
assert_eq!(
1,
Solution::max_removal(vec![2, 0, 2], vec![vec![0, 2], vec![0, 2], vec![1, 1]])
);
assert_eq!(
2,
Solution::max_removal(
vec![1, 1, 1, 1],
vec![vec![1, 3], vec![0, 2], vec![1, 3], vec![1, 2]]
)
);
assert_eq!(
-1,
Solution::max_removal(vec![1, 2, 3, 4], vec![vec![0, 3]])
);
}
}
// Accepted solution for LeetCode #3362: Zero Array Transformation III
function maxRemoval(nums: number[], queries: number[][]): number {
queries.sort((a, b) => a[0] - b[0]);
const pq = new MaxPriorityQueue<number>();
const n = nums.length;
const d: number[] = Array(n + 1).fill(0);
let [s, j] = [0, 0];
for (let i = 0; i < n; i++) {
s += d[i];
while (j < queries.length && queries[j][0] <= i) {
pq.enqueue(queries[j][1]);
j++;
}
while (s < nums[i] && !pq.isEmpty() && pq.front() >= i) {
s++;
d[pq.dequeue() + 1]--;
}
if (s < nums[i]) {
return -1;
}
}
return pq.size();
}
Use this to step through a reusable interview workflow for this problem.
Try every possible combination of choices. With n items each having two states (include/exclude), the search space is 2ⁿ. Evaluating each combination takes O(n), giving O(n × 2ⁿ). The recursion stack or subset storage uses O(n) space.
Greedy algorithms typically sort the input (O(n log n)) then make a single pass (O(n)). The sort dominates. If the input is already sorted or the greedy choice can be computed without sorting, time drops to O(n). Proving greedy correctness (exchange argument) is harder than the implementation.
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: Locally optimal choices may fail globally.
Usually fails on: Counterexamples appear on crafted input orderings.
Fix: Verify with exchange argument or monotonic objective before committing.