leetcode/solution/3300-3399/3355.Zero Array Transformation I

comments	difficulty	edit_url	rating	source	tags
true	Medium	https://github.com/doocs/leetcode/edit/main/solution/3300-3399/3355.Zero%20Array%20Transformation%20I/README_EN.md	1591	Weekly Contest 424 Q2	Array Prefix Sum

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:

  <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

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.

Python3

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

Java

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;
    }
}

C++

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;
    }
};

Go

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
}

TypeScript

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;
}