3362. Zero Array Transformation III LeetCode Solution

Last updated: March 6, 2025

In this guide, you will get 3362. Zero Array Transformation III LeetCode Solution with the best time and space complexity. The solution to Zero Array Transformation III problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Zero Array Transformation III solution in C++
Zero Array Transformation III solution in Java
Zero Array Transformation III solution in Python
Additional Resources

3362. Zero Array Transformation III LeetCode Solution image

Problem Statement of Zero Array Transformation III

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.

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.

Using queries[0], decrement nums[0] and nums[2] by 1 and nums[1] by 0.
Using 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 <= 105
0 <= nums[i] <= 105
1 <= queries.length <= 105
queries[i].length == 2
0 <= li <= ri < nums.length

Complexity Analysis

Time Complexity: O(n + q\log q)
Space Complexity: O(q)

3362. Zero Array Transformation III LeetCode Solution in C++

class Solution {
 public:
  int maxRemoval(vector<int>& nums, vector<vector<int>>& queries) {
    int queryIndex = 0;
    priority_queue<int> available;                        // available `r`s
    priority_queue<int, vector<int>, greater<>> running;  // running `r`s

    ranges::sort(queries);

    for (int i = 0; i < nums.size(); ++i) {
      while (queryIndex < queries.size() && queries[queryIndex][0] <= i)
        available.push(queries[queryIndex++][1]);
      while (!running.empty() && running.top() < i)
        running.pop();
      while (nums[i] > running.size()) {
        if (available.empty() || available.top() < i)
          return -1;
        running.push(available.top()), available.pop();
      }
    }

    return available.size();
  }
};
/* code provided by PROGIEZ */

3362. Zero Array Transformation III LeetCode Solution in Java

class Solution {
  public int maxRemoval(int[] nums, int[][] queries) {
    int queryIndex = 0;
    Queue<Integer> available = new PriorityQueue<>(Collections.reverseOrder()); // available `r`s
    Queue<Integer> running = new PriorityQueue<>();                             // running `r`s

    Arrays.sort(queries, (a, b) -> Integer.compare(a[0], b[0]));

    for (int i = 0; i < nums.length; ++i) {
      while (queryIndex < queries.length && queries[queryIndex][0] <= i)
        available.offer(queries[queryIndex++][1]);
      while (!running.isEmpty() && running.peek() < i)
        running.poll();
      while (nums[i] > running.size()) {
        if (available.isEmpty() || available.peek() < i)
          return -1;
        running.offer(available.poll());
      }
    }

    return available.size();
  }
}
// code provided by PROGIEZ

3362. Zero Array Transformation III LeetCode Solution in Python

from sortedcontainers import SortedList


class Solution:
  def maxRemoval(self, nums: list[int], queries: list[list[int]]) -> int:
    q = collections.deque(sorted(queries))
    available = SortedList()  # available `r`s
    running = SortedList()  # running `r`s

    for i, num in enumerate(nums):
      while q and q[0][0] <= i:
        available.add(q.popleft()[1])
      while running and running[0] < i:
        running.pop(0)
      while num > len(running):
        if not available or available[-1] < i:
          return -1
        running.add(available.pop())

    return len(available)
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents