3489. Zero Array Transformation IV LeetCode Solution

Last updated: March 17, 2025

In this guide, you will get 3489. Zero Array Transformation IV LeetCode Solution with the best time and space complexity. The solution to Zero Array Transformation IV 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 IV solution in C++
Zero Array Transformation IV solution in Java
Zero Array Transformation IV solution in Python
Additional Resources

3489. Zero Array Transformation IV LeetCode Solution image

Problem Statement of Zero Array Transformation IV

You are given an integer array nums of length n and a 2D array queries, where queries[i] = [li, ri, vali].
Each queries[i] represents the following action on nums:

Select a subset of indices in the range [li, ri] from nums.
Decrement the value at each selected index by exactly vali.

A Zero Array is an array with all its elements equal to 0.
Return the minimum possible non-negative value of k, such that after processing the first k queries in sequence, nums becomes a Zero Array. If no such k exists, return -1.

Example 1:

Input: nums = [2,0,2], queries = [[0,2,1],[0,2,1],[1,1,3]]
Output: 2
Explanation:

For query 0 (l = 0, r = 2, val = 1):

Decrement the values at indices [0, 2] by 1.
The array will become [1, 0, 1].

For query 1 (l = 0, r = 2, val = 1):

Decrement the values at indices [0, 2] by 1.
The array will become [0, 0, 0], which is a Zero Array. Therefore, the minimum value of k is 2.

Example 2:

Input: nums = [4,3,2,1], queries = [[1,3,2],[0,2,1]]
Output: -1
Explanation:
It is impossible to make nums a Zero Array even after all the queries.

Example 3:

Input: nums = [1,2,3,2,1], queries = [[0,1,1],[1,2,1],[2,3,2],[3,4,1],[4,4,1]]
Output: 4
Explanation:

For query 0 (l = 0, r = 1, val = 1):

Decrement the values at indices [0, 1] by 1.
The array will become [0, 1, 3, 2, 1].

For query 1 (l = 1, r = 2, val = 1):

Decrement the values at indices [1, 2] by 1.
The array will become [0, 0, 2, 2, 1].

For query 2 (l = 2, r = 3, val = 2):

Decrement the values at indices [2, 3] by 2.
The array will become [0, 0, 0, 0, 1].

For query 3 (l = 3, r = 4, val = 1):

Decrement the value at index 4 by 1.
The array will become [0, 0, 0, 0, 0]. Therefore, the minimum value of k is 4.

Example 4:

Input: nums = [1,2,3,2,6], queries = [[0,1,1],[0,2,1],[1,4,2],[4,4,4],[3,4,1],[4,4,5]]
Output: 4

Constraints:

1 <= nums.length <= 10
0 <= nums[i] <= 1000
1 <= queries.length <= 1000
queries[i] = [li, ri, vali]
0 <= li <= ri < nums.length
1 <= vali <= 10

Complexity Analysis

Time Complexity: O(q \cdot 2^n)
Space Complexity: O(q \cdot 2^n)

3489. Zero Array Transformation IV LeetCode Solution in C++

class Solution {
 public:
  int minZeroArray(vector<int>& nums, vector<vector<int>>& queries) {
    if (all_of(nums.begin(), nums.end(), [](int num) { return num == 0; }))
      return 0;

    const int n = nums.size();
    vector<unordered_set<int>> subsetSums(n);

    for (int i = 0; i < n; ++i)
      subsetSums[i].insert(0);

    for (int k = 0; k < queries.size(); ++k) {
      const int l = queries[k][0];
      const int r = queries[k][1];
      const int val = queries[k][2];
      for (int i = l; i <= r; ++i) {
        vector<int> sums;
        for (const int subsetSum : subsetSums[i])
          sums.push_back(subsetSum + val);
        for (const int sum : sums)
          subsetSums[i].insert(sum);
      }
      if (canFormAllNumbers(subsetSums, nums))
        return k + 1;
    }

    return -1;
  }

  bool canFormAllNumbers(const vector<unordered_set<int>>& subsetSums,
                         const vector<int>& nums) {
    for (int i = 0; i < nums.size(); ++i)
      if (!subsetSums[i].contains(nums[i]))
        return false;
    return true;
  }
};
/* code provided by PROGIEZ */

3489. Zero Array Transformation IV LeetCode Solution in Java

class Solution {
  public int minZeroArray(int[] nums, int[][] queries) {
    if (Arrays.stream(nums).allMatch(num -> num == 0))
      return 0;

    final int n = nums.length;
    Set<Integer>[] subsetSums = new Set[n];

    for (int i = 0; i < n; ++i)
      subsetSums[i] = new HashSet<>(List.of(0));

    for (int k = 0; k < queries.length; ++k) {
      final int l = queries[k][0];
      final int r = queries[k][1];
      final int val = queries[k][2];
      for (int i = l; i <= r; ++i) {
        List<Integer> sums = new ArrayList<>();
        for (final int subsetSum : subsetSums[i])
          sums.add(subsetSum + val);
        subsetSums[i].addAll(sums);
      }
      if (IntStream.range(0, n).allMatch(i -> subsetSums[i].contains(nums[i])))
        return k + 1;
    }

    return -1;
  }
}
// code provided by PROGIEZ

3489. Zero Array Transformation IV LeetCode Solution in Python

class Solution:
  def minZeroArray(self, nums: list[int], queries: list[list[int]]) -> int:
    if all(num == 0 for num in nums):
      return 0

    n = len(nums)
    subsetSums = [{0} for _ in range(n)]

    for k, (l, r, val) in enumerate(queries):
      for i in range(l, r + 1):
        newSums = {subsetSum + val for subsetSum in subsetSums[i]}
        subsetSums[i].update(newSums)
      if all(nums[i] in subsetSums[i] for i in range(n)):
        return k + 1

    return -1
 # code by PROGIEZ

Additional Resources

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

Table of Contents