3639. Zero Array Transformation I¶

Difficulty: Medium

3639. Zero Array Transformation I

Medium

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

For each queries[i]:

Select a subset of indices within the range [l_i, r_i] 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.

A subset of an array is a selection of elements (possibly none) of the array.

Example 1:

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:

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⁵
0 <= nums[i] <= 10⁵
1 <= queries.length <= 10⁵
queries[i].length == 2
0 <= l_i <= r_i < nums.length

Solution¶

class Solution {
    public boolean isZeroArray(int[] nums, int[][] queries) {
        int n = nums.length;
        int arr[] = new int[n];
        for (int current_query[] : queries) {
            int l = current_query[0];
            int r = current_query[1];
            arr[l]++; 
            if (r + 1 < n) arr[r + 1]--;
        }
        for (int i = 1; i < n; i++) arr[i] = arr[i - 1] + arr[i];
        for (int i = 0; i < n; i++) {
            if (arr[i] < nums[i]) return false;
        }
        return true;
    }
}

Complexity Analysis¶

Time Complexity: O(?)
Space Complexity: O(?)

Approach¶

Detailed explanation of the approach will be added here