zero-array-transformation-i

java

python3

python

javascript

typescript

csharp

golang

kotlin

swift

rust

ruby

dart

scala

elixir

erlang

racket

cangjie

bash

mysql

mssql

postgresql

oraclesql

pythondata

Algorithms

You are given an integer array <code>nums</code> of length <code>n</code> and a 2D array <code>queries</code>, where <code>queries[i] = [li, ri]</code>.

For each <code>queries[i]</code>:

<ul>
	<li>Select a subset of indices within the range <code>[li, ri]</code> in <code>nums</code>.</li>
	<li>Decrement the values at the selected indices by 1.</li>
</ul>

A Zero Array is an array where all elements are equal to 0.

Return <code>true</code> if it is possible to transform <code>nums</code> into a Zero Array after processing all the queries sequentially, otherwise return <code>false</code>.

&nbsp;
Example 1:

<div class="example-block">
Input: nums = [1,0,1], queries = [[0,2]]

Output: true

Explanation:

<ul>
	<li>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>
</ul>
</div>

Example 2:

<div class="example-block">
Input: nums = [4,3,2,1], queries = [[1,3],[0,2]]

Output: false

Explanation:

<ul>
	<li>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>For i = 1:
	<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>
</ul>
</div>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= nums.length &lt;= 105</code></li>
	<li><code>0 &lt;= nums[i] &lt;= 105</code></li>
	<li><code>1 &lt;= queries.length &lt;= 105</code></li>
	<li><code>queries[i].length == 2</code></li>
	<li><code>0 &lt;= li &lt;= ri &lt; nums.length</code></li>
</ul>

第 424 场周赛

weekly-contest-424

isZeroArray

高级工程师

Zero Array Transformation I

Zero Array Transformation IV

zero-array-transformation-iv

零数组变换 IV

Array

Prefix Sum

给定一个长度为 <code>n</code> 的整数数组 <code>nums</code> 和一个二维数组 <code>queries</code>，其中 <code>queries[i] = [li, ri]</code>。

对于每个查询&nbsp;<code>queries[i]</code>：

<ul>
	<li>在&nbsp;<code>nums</code>&nbsp;的下标范围&nbsp;<code>[li, ri]</code>&nbsp;内选择一个下标 子集。</li>
	<li>将选中的每个下标对应的元素值减 1。</li>
</ul>

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

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

&nbsp;

示例 1：

<div class="example-block">
输入： nums = [1,0,1], queries = [[0,2]]

输出： true

解释：

<ul>
	<li>对于 i = 0：

	<ul>
		<li>选择下标子集 <code>[0, 2]</code> 并将这些下标处的值减 1。</li>
		<li>数组将变为 <code>[0, 0, 0]</code>，这是一个零数组。</li>
	</ul>
	</li>
</ul>
</div>

示例 2：

<div class="example-block">
输入： nums = [4,3,2,1], queries = [[1,3],[0,2]]

输出： false

解释：

<ul>
	<li>对于 i = 0：&nbsp;

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

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= nums.length &lt;= 105</code></li>
	<li><code>0 &lt;= nums[i] &lt;= 105</code></li>
	<li><code>1 &lt;= queries.length &lt;= 105</code></li>
	<li><code>queries[i].length == 2</code></li>
	<li><code>0 &lt;= li &lt;= ri &lt; nums.length</code></li>
</ul>