Skip to content

3356. Zero Array Transformation II 👍

  • Time: $O(n)$
  • Space: $O(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
class Solution {
 public:
  int minZeroArray(vector<int>& nums, vector<vector<int>>& queries) {
    vector<int> line(nums.size() + 1);
    int decrement = 0;
    int k = 0;

    for (int i = 0; i < nums.size(); ++i) {
      while (decrement + line[i] < nums[i]) {
        if (k == queries.size())
          return -1;
        const int l = queries[k][0];
        const int r = queries[k][1];
        const int val = queries[k][2];
        ++k;
        if (r < i)
          continue;
        line[max(l, i)] += val;
        line[r + 1] -= val;
      }
      decrement += line[i];
    }

    return k;
  }
};

 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
class Solution {
  public int minZeroArray(int[] nums, int[][] queries) {
    int[] line = new int[nums.length + 1];
    int decrement = 0;
    int k = 0;

    for (int i = 0; i < nums.length; ++i) {
      while (decrement + line[i] < nums[i]) {
        if (k == queries.length)
          return -1;
        final int l = queries[k][0];
        final int r = queries[k][1];
        final int val = queries[k][2];
        ++k;
        if (r < i)
          continue;
        line[Math.max(l, i)] += val;
        line[r + 1] -= val;
      }
      decrement += line[i];
    }

    return k;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
  def minZeroArray(self, nums: list[int], queries: list[list[int]]) -> int:
    line = [0] * (len(nums) + 1)
    decrement = 0
    k = 0

    for i, num in enumerate(nums):
      while decrement + line[i] < num:
        if k == len(queries):
          return -1
        l, r, val = queries[k]
        k += 1
        if r < i:
          continue
        line[max(l, i)] += val
        line[r + 1] -= val
      decrement += line[i]

    return k