3355. Zero Array Transformation I

Problem Link

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]]

Output: true

Explanation:

• For i = 0:

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

Example 2:

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

Output: false

Explanation:

• For i = 0:

  <ul>
  	<li>Select the subset of indices as <code>[1, 2, 3]</code> and decrement the values at these indices by 1.</li>
  	<li>The array will become <code>[4, 2, 1, 0]</code>.</li>
  </ul>
  </li>
  <li><strong>For i = 1:</strong>
  <ul>
  	<li>Select the subset of indices as <code>[0, 1, 2]</code> and decrement the values at these indices by 1.</li>
  	<li>The array will become <code>[3, 1, 0, 0]</code>, which is not a Zero Array.</li>
  </ul>
  </li>
  

 

Constraints:

• 1 <= nums.length <= 105
• 0 <= nums[i] <= 105
• 1 <= queries.length <= 105
• queries[i].length == 2
• 0 <= li <= ri < nums.length

Solution

---

Python3

class Solution:
    def isZeroArray(self, nums: List[int], queries: List[List[int]]) -> bool:
        N = len(nums)
        lines = [0] * (N + 1)
 
        for l, r in queries:
            lines[l] -= 1
            lines[r + 1] += 1
        
        for i in range(N):
            lines[i + 1] += lines[i]
        
        for i in range(N):
            if nums[i] + lines[i] > 0:
                return False
 
        return True