3355. Zero Array Transformation I

Posted on Edited on In

3355. Zero Array Transformation I

Description

You are given an integer array nums of length n and a 2D array queries, where queries[i] = [li, ri].

For each queries[i]:

  • Select a subset of indices within the range [li, ri] in nums.
  • Decrement the values at the selected indices by 1.

A Zero Array is an array where all elements are equal to 0.

Return true if it is possible to transform nums into a Zero Array after processing all the queries sequentially, otherwise return false.

Example 1:

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

Output: true

Explanation:

  • For i = 0:

    • Select the subset of indices as [0, 2] and decrement the values at these indices by 1.
    • The array will become [0, 0, 0], which is a Zero Array.

Example 2:

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

Output: false

Explanation:

  • For i = 0:

    • Select the subset of indices as [1, 2, 3] and decrement the values at these indices by 1.
    • The array will become [4, 2, 1, 0].

  • For i = 1:

    • Select the subset of indices as [0, 1, 2] and decrement the values at these indices by 1.
    • The array will become [3, 1, 0, 0], which is not a Zero Array.

Constraints:

  • 1 <= nums.length <= 10^5
  • 0 <= nums[i] <= 10^5
  • 1 <= queries.length <= 10^5
  • queries[i].length == 2
  • 0 <= li <= ri < nums.length

Hints/Notes

Solution

Language: C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    bool isZeroArray(vector<int>& nums, vector<vector<int>>& queries) {
        int n = nums.size();
        vector<int> diffs(n + 1, 0);
        for (auto& q : queries) {
            int l = q[0], r = q[1];
            diffs[l] -= 1;
            diffs[r + 1] += 1;
        }
        partial_sum(diffs.begin(), diffs.end(), diffs.begin());
        for (int i = 0; i < n; i++) {
            nums[i] = nums[i] + diffs[i];
            if (nums[i] > 0) {
                return false;
            }

        }
        return true;
    }
};