Welcome to Subscribe On Youtube

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:

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 <= 105
  • 0 <= nums[i] <= 105
  • 1 <= queries.length <= 105
  • queries[i].length == 2
  • 0 <= li <= ri < nums.length

Solutions

Solution 1: Difference Array

We can use a difference array to solve this problem.

Define an array $d$ of length $n + 1$, with all initial values set to $0$. For each query $[l, r]$, we add $1$ to $d[l]$ and subtract $1$ from $d[r + 1]$.

Then we traverse the array $d$ within the range $[0, n - 1]$, accumulating the prefix sum $s$. If $\textit{nums}[i] > s$, it means $\textit{nums}$ cannot be converted to a zero array, so we return $\textit{false}$.

After traversing, return $\textit{true}$.

The time complexity is $O(n + m)$, and the space complexity is $O(n)$. Here, $n$ and $m$ are the lengths of the array $\textit{nums}$ and the number of queries, respectively.

  • class Solution { public boolean isZeroArray(int[] nums, int[][] queries) { int n = nums.length; int[] d = new int[n + 1]; for (var q : queries) { int l = q[0], r = q[1]; ++d[l]; --d[r + 1]; } for (int i = 0, s = 0; i < n; ++i) { s += d[i]; if (nums[i] > s) { return false; } } return true; } } 
  • class Solution { public: bool isZeroArray(vector<int>& nums, vector<vector<int>>& queries) { int n = nums.size(); int d[n + 1]; memset(d, 0, sizeof(d)); for (const auto& q : queries) { int l = q[0], r = q[1]; ++d[l]; --d[r + 1]; } for (int i = 0, s = 0; i < n; ++i) { s += d[i]; if (nums[i] > s) { return false; } } return true; } }; 
  • class Solution: def isZeroArray(self, nums: List[int], queries: List[List[int]]) -> bool: d = [0] * (len(nums) + 1) for l, r in queries: d[l] += 1 d[r + 1] -= 1 s = 0 for x, y in zip(nums, d): s += y if x > s: return False return True 
  • func isZeroArray(nums []int, queries [][]int) bool { d := make([]int, len(nums)+1) for _, q := range queries { l, r := q[0], q[1] d[l]++ d[r+1]-- } s := 0 for i, x := range nums { s += d[i] if x > s { return false } } return true } 
  • function isZeroArray(nums: number[], queries: number[][]): boolean { const n = nums.length; const d: number[] = Array(n + 1).fill(0); for (const [l, r] of queries) { ++d[l]; --d[r + 1]; } for (let i = 0, s = 0; i < n; ++i) { s += d[i]; if (nums[i] > s) { return false; } } return true; }

All Problems

All Solutions