Zero Array Transformation I

Leet Code Link - https://leetcode.com/problems/zero-array-transformation-i/description/

Complexity - Medium

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:

Input: nums = [1,0,1], queries = [0,2](/shilpathota/99-leetcode-solutions/wiki/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](/shilpathota/99-leetcode-solutions/wiki/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 <= 105
0 <= nums[i] <= 105
1 <= queries.length <= 105
queries[i].length == 2
0 <= li <= ri < nums.length

Solution

I have tried a brute force solution where I created an array and as I iterate through each of the limits in the query I increment it. Finally I compare it with the nums and if it does not gets zero by that number at that index I returned false. This is throwing me Timeout exception

class Solution {
    public boolean isZeroArray(int[] nums, int[][] queries) {
        int[] arr = new int[nums.length];
        for(int i=0;i<queries.length;i++){
            for(int j=queries[i][0];j<=queries[i][1];j++){
                arr[j]++;
            }
        }
                for(int i=0;i<nums.length;i++){
                    if(nums[i]>arr[i]&&nums[i]-arr[i]!=0){
                        return false;
                    }
                }
                return true;
    }
}

• The best way to solve this problem is marking the arr with +1 for the queries starting window and -1 for the ending window.
• This way we have to mark only the window sizes in the arr
• As we iterate through numbers calculate the prefix sum of the arr and compare with nums array.

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

Time Complexity and Space Complexity is O(N)