LeetCode 2772 - Apply Operations to Make All Array Elements Equal to Zero

Difficulty: 🟡 Medium
Topics: Array, Prefix Sum

Solution

Problem Understanding

The problem gives us an integer array nums and an integer k. We are allowed to repeatedly choose any contiguous subarray of length k and decrease every element inside that subarray by 1.

Our goal is to determine whether it is possible to make every element in the array equal to 0 after performing any number of these operations.

An important detail is that every operation affects exactly k consecutive elements. We cannot decrease individual elements independently. This creates dependencies between nearby positions in the array.

For example, if k = 3, then choosing index i means we decrease:

nums[i], nums[i+1], nums[i+2]

all at the same time.

The array is initially non-negative, and operations only decrease values. Therefore, once an element becomes negative, there is no way to recover it. That means every operation choice must be carefully controlled.

The constraints are large:

nums.length can be up to 10^5
nums[i] can be up to 10^6

These limits immediately rule out any simulation that repeatedly applies operations one by one in a naive way. We need an algorithm that processes the array efficiently, ideally in linear time.

There are several important edge cases to think about early:

When k = 1, every element can be reduced independently, so the answer is always true.
When k = nums.length, the only possible operation affects the whole array. Therefore, all elements must already be equal for the answer to be true.
Arrays containing zeros require careful handling because we must avoid accidentally making them negative.
Positions near the end of the array are especially important because once we pass index n - k, we can no longer start new operations there.

The key challenge is deciding, while scanning the array, how many operations must start at each position so that every element eventually becomes zero.

Approaches

Brute Force Approach

A straightforward approach is to simulate the process directly.

We iterate through the array from left to right. At each index i, if nums[i] is greater than 0, we must apply operations starting at i exactly nums[i] times, because this is the only remaining opportunity to reduce that position before moving forward.

Each operation decreases the next k elements by 1.

For example:

nums = [2,2,3,1,1,0], k = 3

At index 0, we apply the operation twice:

[2,2,3,1,1,0]
-> [1,1,2,1,1,0]
-> [0,0,1,1,1,0]

Then continue to the next index.

This approach is correct because processing from left to right greedily ensures that every element becomes zero before we move past it.

However, the problem is efficiency. If an element has value x, we may perform x operations, and each operation touches k elements.

In the worst case:

nums[i] can be 10^6
n can be 10^5

This becomes far too slow.

Key Insight for the Optimal Solution

The crucial observation is that we do not need to physically apply every operation to every element.

Instead, we only need to know how many active operations currently affect each index.

Suppose we process the array from left to right.

At position i:

Some earlier operations are still affecting this index.
Let current_decrement represent the total reduction already applied to nums[i].

Then the effective value at index i is:

nums[i] - current_decrement

If this value is:

Negative, we already over-decreased the element, so the answer is false.
Positive, we must start exactly that many operations at index i.
Zero, no new operation is needed.

The next challenge is efficiently tracking when operations stop affecting future indices.

This is where a difference array technique becomes useful.

When we start x operations at index i:

They begin affecting positions immediately.
They stop affecting positions after index i + k - 1.

So we can:

Add x to the current active decrement.
Schedule removal of x at position i + k.

This lets us process the entire array in linear time.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n × k × max(nums[i]))	O(1)	Simulates every operation explicitly
Optimal	O(n)	O(n)	Uses prefix sum style difference tracking

Algorithm Walkthrough

Create a difference array called difference of size n + 1, initialized with zeros.

This array tracks when the effect of operations expires. 2. Maintain a variable called current_decrement.

This represents how much reduction is currently affecting the current index due to previously started operations. 3. Iterate through the array from left to right.

At each index i, first apply any scheduled expiration:

current_decrement += difference[i]

Since difference[i] may contain negative values, this removes expired operations. 4. Compute the remaining value at the current index:

remaining = nums[i] - current_decrement

This tells us how much more reduction this position still needs. 5. If remaining < 0, return false.

This means previous operations already decreased the element too much. 6. If remaining == 0, continue.

This position is already satisfied. 7. If remaining > 0, we must start exactly remaining operations at index i.

There is no alternative because once we move beyond this index, no future operation can affect it. 8. Before starting operations, verify that a subarray of size k starting at i fits inside the array.

If:

i + k > n

return false. 9. Apply the operations logically:

Increase current_decrement by remaining
Schedule removal at index i + k

Conceptually:

current_decrement += remaining
difference[i + k] -= remaining

Continue until the entire array is processed.
If no invalid state occurs, return true.

Why it works

The algorithm relies on a greedy invariant.

When processing index i, the only chance to reduce nums[i] further is to start operations exactly at i. Any later operation starts too far to the right and cannot affect this position.

Therefore:

If the current effective value is positive, we are forced to start that many operations.
If the effective value is negative, we already made an irreversible mistake.

Because every decision is forced and uniquely determined, the greedy approach is correct.

The difference array allows us to efficiently track the cumulative effect of all active operations without explicitly modifying every affected element.

Python Solution

from typing import List

class Solution:
    def checkArray(self, nums: List[int], k: int) -> bool:
        n = len(nums)

        difference = [0] * (n + 1)
        current_decrement = 0

        for i in range(n):
            current_decrement += difference[i]

            remaining = nums[i] - current_decrement

            if remaining < 0:
                return False

            if remaining == 0:
                continue

            if i + k > n:
                return False

            current_decrement += remaining
            difference[i + k] -= remaining

        return True

The implementation follows the greedy strategy exactly.

The difference array stores scheduled changes to the active decrement total. Whenever we reach an index, we first apply any pending updates from earlier operations.

The variable current_decrement acts like a running prefix sum. It tells us how many total decrements currently affect the current position.

At each index:

We compute how much value still remains.
If the value is negative, the array cannot be repaired.
If the value is positive, we must start that many operations immediately.

Instead of updating all k elements directly, we only:

Increase the active decrement count now.
Schedule its removal later.

This converts what would normally be an expensive range update into constant time work per index.

Go Solution

func checkArray(nums []int, k int) bool {
	n := len(nums)

	difference := make([]int, n+1)
	currentDecrement := 0

	for i := 0; i < n; i++ {
		currentDecrement += difference[i]

		remaining := nums[i] - currentDecrement

		if remaining < 0 {
			return false
		}

		if remaining == 0 {
			continue
		}

		if i+k > n {
			return false
		}

		currentDecrement += remaining
		difference[i+k] -= remaining
	}

	return true
}

The Go implementation mirrors the Python logic closely.

Slices are used instead of Python lists. Since Go integers are large enough for the problem constraints, standard int values are sufficient.

The difference array is allocated with size n + 1 so that scheduling removal at index i + k is always safe.

Unlike Python, Go does not have built-in dynamic integer resizing semantics, but the maximum cumulative values remain comfortably within integer range for typical Go environments.

Worked Examples

Example 1

nums = [2,2,3,1,1,0]
k = 3

Initial state:

difference = [0,0,0,0,0,0,0]
current_decrement = 0

i	difference[i]	current_decrement	nums[i]	remaining	Action
0	0	0	2	2	Start 2 operations
1	0	2	2	0	Continue
2	0	2	3	1	Start 1 operation
3	-2	1	1	0	Continue
4	0	1	1	0	Continue
5	-1	0	0	0	Continue

Detailed transitions:

At index 0

remaining = 2 - 0 = 2

We must start 2 operations.

Update:

current_decrement = 2
difference[3] -= 2

At index 2

remaining = 3 - 2 = 1

Start 1 more operation.

Update:

current_decrement = 3
difference[5] -= 1

At index 3

Apply expiration:

current_decrement += difference[3]
current_decrement = 3 + (-2) = 1

Everything remains valid.

Final answer:

true

Example 2

nums = [1,3,1,1]
k = 2

Initial state:

difference = [0,0,0,0,0]
current_decrement = 0

i	difference[i]	current_decrement	nums[i]	remaining	Action
0	0	0	1	1	Start 1 operation
1	0	1	3	2	Start 2 operations
2	-1	2	1	-1	Invalid

At index 2:

remaining = 1 - 2 = -1

This means earlier operations already decreased the element too much.

Therefore:

false

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each index is processed once
Space	O(n)	Difference array stores scheduled updates

The algorithm performs constant work for every element in the array. No nested iteration occurs, and no operation explicitly updates an entire subarray.

The difference array allows range operations to be represented compactly, which reduces the complexity from potentially enormous repeated updates down to linear time.

Test Cases

from typing import List

class Solution:
    def checkArray(self, nums: List[int], k: int) -> bool:
        n = len(nums)

        difference = [0] * (n + 1)
        current_decrement = 0

        for i in range(n):
            current_decrement += difference[i]

            remaining = nums[i] - current_decrement

            if remaining < 0:
                return False

            if remaining == 0:
                continue

            if i + k > n:
                return False

            current_decrement += remaining
            difference[i + k] -= remaining

        return True

solution = Solution()

assert solution.checkArray([2,2,3,1,1,0], 3) == True   # provided valid example
assert solution.checkArray([1,3,1,1], 2) == False      # provided invalid example

assert solution.checkArray([0], 1) == True             # single zero element
assert solution.checkArray([5], 1) == True             # k=1 always works
assert solution.checkArray([1,1,1], 3) == True         # entire array reduced together
assert solution.checkArray([1,2,1], 3) == False        # unequal values when k=n

assert solution.checkArray([0,0,0], 2) == True         # already all zeros
assert solution.checkArray([3,3,3], 1) == True         # independent reductions
assert solution.checkArray([1,1,0], 2) == False        # cannot finish last element

assert solution.checkArray([2,2,2,2], 2) == True       # repeated overlapping operations
assert solution.checkArray([2,1,2], 2) == False        # negative remainder appears

assert solution.checkArray([10**6] * 1000, 1) == True  # large values stress test

Test	Why
`[2,2,3,1,1,0], k=3`	Validates standard successful case
`[1,3,1,1], k=2`	Validates impossible configuration
`[0], k=1`	Smallest valid input
`[5], k=1`	Every element independently reducible
`[1,1,1], k=3`	Entire array operated together
`[1,2,1], k=3`	Checks impossible full-array operation
`[0,0,0], k=2`	Already solved input
`[3,3,3], k=1`	Independent element handling
`[1,1,0], k=2`	End-of-array failure case
`[2,2,2,2], k=2`	Multiple overlapping operations
`[2,1,2], k=2`	Detects over-decrement bug
`[10^6 repeated], k=1`	Large-value stress test

Edge Cases

Case 1: `k = 1`

When k = 1, each operation affects only a single element. This means every element can be reduced independently until it reaches zero.

A buggy implementation might overcomplicate this situation or accidentally apply shared state incorrectly. The current implementation handles it naturally because each operation expires immediately at the next index.

For any non-negative array, the answer is always true.

Case 2: `k = nums.length`

In this situation, the only possible operation affects the entire array at once.

Therefore, all elements must be equal. Otherwise, reducing the whole array repeatedly will eventually make some elements negative before others reach zero.

The implementation handles this correctly because once we move beyond index 0, no further operations can begin. If any later element still needs adjustment, the condition:

i + k > n

detects the impossibility.

Case 3: Over-Decrementing an Element

A dangerous scenario occurs when earlier operations reduce a future element too much.

Example:

nums = [1,3,1,1]
k = 2

After satisfying the first two positions, index 2 becomes effectively negative.

Without explicitly checking for:

remaining < 0

an implementation could incorrectly continue processing.

The solution immediately returns false when this occurs, guaranteeing correctness.

Case 4: Operations Near the End of the Array

Positions near the end are tricky because there may not be enough remaining elements to form a subarray of length k.