Skip to content

3489. Zero Array Transformation IV 👍

  • Time: $O(q \cdot 2^n)$
  • Space: $O(q \cdot 2^n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
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;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
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