What is the key pattern for Zero Array Transformation I?

The main pattern is using a difference array combined with prefix sums to track range operations efficiently.

Can I modify the original array directly for each query?

No, directly modifying the array per query is inefficient and may lead to timeouts for large inputs.

Why do we use a prefix sum after the difference array?

Prefix sums convert the difference array into actual net values at each index to check if they can become zero.

What should I watch out for with overlapping queries?

Ensure the difference array correctly accumulates overlapping range effects; otherwise, zero validation can fail.

What is the expected time complexity for this problem?

The solution runs in O(n + m) time, where n is nums length and m is the number of queries, due to efficient difference array and prefix sum usage.

#3355

Medium

auto_awesome前缀和

LeetCode 题解工作台

零数组变换 I

给定一个长度为 n 的整数数组 nums 和一个二维数组 queries ，其中 queries[i] = [l i , r i ] 。对于每个查询 queries[i] ：在 nums 的下标范围 [l i , r i ] 内选择一个下标子集。将选中的每个下标对应的元素值减 1。零数组…

数组前缀和

题目描述

给定一个长度为 n 的整数数组 nums 和一个二维数组 queries，其中 queries[i] = [l_i, r_i]。

对于每个查询 queries[i]：

在 nums 的下标范围 [l_i, r_i] 内选择一个下标子集。
将选中的每个下标对应的元素值减 1。

零数组 是指所有元素都等于 0 的数组。

如果在按顺序处理所有查询后，可以将 nums 转换为 零数组 ，则返回 true，否则返回 false。

示例 1：

输入： nums = [1,0,1], queries = [[0,2]]

输出： true

解释：

对于 i = 0：
- 选择下标子集 [0, 2] 并将这些下标处的值减 1。
- 数组将变为 [0, 0, 0]，这是一个零数组。

示例 2：

输入： nums = [4,3,2,1], queries = [[1,3],[0,2]]

输出： false

解释：

对于 i = 0：
- 选择下标子集 [1, 2, 3] 并将这些下标处的值减 1。
- 数组将变为 [4, 2, 1, 0]。
对于 i = 1：
- 选择下标子集 [0, 1, 2] 并将这些下标处的值减 1。
- 数组将变为 [3, 1, 0, 0]，这不是一个零数组。

提示：

1 <= nums.length <= 10⁵
0 <= nums[i] <= 10⁵
1 <= queries.length <= 10⁵
queries[i].length == 2
0 <= l_i <= r_i < nums.length

lightbulb

解题思路

方法一：差分数组

我们可以使用差分数组来解决这个问题。

定义一个长度为 $n + 1$ 的数组 $d$ ，初始值全部为 $0$ 。对于每个查询 $[l, r]$ ，我们将 $d[l]$ 加 $1$ ，将 $d[r + 1]$ 减 $1$ 。

然后我们遍历数组 $d$ 在 $[0, n - 1]$ 范围内的每个元素，累加前缀和 $s$ ，如果 $\textit{nums}[i] > s$ ，说明 $\textit{nums}$ 不能转换为零数组，返回 $\textit{false}$ 。

遍历结束后，返回 $\textit{true}$ 。

时间复杂度 $O(n + m)$ ，空间复杂度 $O(n)$ 。其中 $n$ 和 $m$ 分别为数组 $\textit{nums}$ 和 $\textit{queries}$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

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

speed

复杂度分析

指标	值
时间	complexity is O(n + m) where n is the length of nums and m is the number of queries, because each query is processed once and prefix sums are computed in a single pass. Space complexity is O(n) for the difference array.
空间	O(n)

psychology

面试官常问的追问

外企场景

question_mark
Check whether you are correctly using a difference array instead of modifying the original array per query.
question_mark
Make sure your prefix sum computation correctly accumulates all range operations.
question_mark
Consider edge cases where queries overlap or cover entire array sections.

warning

常见陷阱

外企场景

error
Updating the original array directly for each query leads to TLE for large n or m.
error
Incorrect handling of diff[r+1] can miscalculate net effects at array boundaries.
error
Forgetting to validate that all elements are zero after prefix sum accumulation.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Allowing queries that increment or decrement by different values, not just ±1.
arrow_right_alt
Checking for partial zero arrays where only a subset must be zero.
arrow_right_alt
Transforming using non-contiguous index sets instead of continuous ranges.

help

常见问题

外企场景

继续练习

#3354 使数组元素等于零 #3356 零数组变换 II #3361 两个字符串的切换距离