Skip to content

3355. Zero Array Transformation I 👍

  • 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
class Solution {
 public:
  bool isZeroArray(vector<int>& nums, vector<vector<int>>& queries) {
    vector<int> line(nums.size() + 1);
    int decrement = 0;

    for (const vector<int>& query : queries) {
      const int l = query[0];
      const int r = query[1];
      ++line[l];
      --line[r + 1];
    }

    for (int i = 0; i < nums.size(); ++i) {
      decrement += line[i];
      if (decrement < 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
class Solution {
  public boolean isZeroArray(int[] nums, int[][] queries) {
    int[] line = new int[nums.length + 1];
    int decrement = 0;

    for (int[] query : queries) {
      final int l = query[0];
      final int r = query[1];
      ++line[l];
      --line[r + 1];
    }

    for (int i = 0; i < nums.length; ++i) {
      decrement += line[i];
      if (decrement < nums[i])
        return false;
    }

    return true;
  }
}

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

    for l, r in queries:
      line[l] += 1
      line[r + 1] -= 1

    for i, num in enumerate(nums):
      decrement += line[i]
      if decrement < num:
        return False

    return True