Abstract / Summary

You can subtract any value from any element and add it to another to eventually make all elements zero if the total sum is zero.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 33% (50k+ submissions).

Typical patterns to solve this problem:

• Array
• Prefix Sum

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided Solution class implements a method checkArray that determines whether a given integer array nums can be transformed into a non-negative array by applying a series of operations constrained by a window size k. The algorithm walks through the array once, maintaining a running adjustment (previous) that reflects the cumulative effect of earlier operations. By using an auxiliary delta array to record when each operation’s influence ends, the method can decide in constant time per element whether the required adjustments are feasible.

Core Logic

The method begins by allocating a helper array delta whose length matches the input array. This array stores the magnitude of the subtraction that starts at each index and will be “canceled out” after k positions.

size  = len(nums)
delta = [0] * size

A variable previous holds the total amount that has been subtracted from the current position due to earlier operations.

previous = 0

The main loop iterates over each element together with its index.

for i, n in enumerate(nums):

Sliding-Window Cancellation

When the current index i reaches or exceeds k, the algorithm removes the contribution of the operation that began k steps earlier. This is achieved by subtracting the stored value from delta[i - k] from previous.

if i >= k:
    previous -= delta[i - k]   # some subarray ends here

This step implements a sliding-window mechanism that ensures previous always reflects the net subtraction affecting the current element only.

Determining the Required Adjustment

The variable remaining represents the amount that still needs to be subtracted from the current element to keep it non-negative after accounting for previous adjustments.

remaining = n - previous

If remaining is negative, the algorithm immediately returns False because the earlier operations have already subtracted more than the current value permits.

if remaining < 0:
    return False

Boundary Validation

When a positive remaining is required, the algorithm checks whether there is enough room to apply an operation of length k. If the operation would extend beyond the array bounds (i + k > size), the transformation is impossible, and the method returns False.

if remaining > 0 and i + k > size:
    return False

Recording the New Operation

If the checks pass, the needed subtraction amount is stored in delta[i]. This records that an operation of magnitude remaining starts at index i and will be undone after k steps. The variable previous is then updated to reflect the new total subtraction affecting the next element.

delta[i] = remaining   # keep track when current subarray ends
previous = n

Successful Completion

If the loop finishes without triggering any early return, the method concludes that the array can be transformed as required and returns True.

return True

Edge Cases Handled

The implementation explicitly guards against three subtle situations:

• Over-subtraction - When the cumulative subtraction exceeds the current element, remaining becomes negative and the method aborts. This prevents the algorithm from producing an invalid negative value.

• Insufficient Length for an Operation - If a positive adjustment is needed near the end of the array and there are fewer than k positions left, the condition i + k > size catches the scenario, ensuring that no operation would spill outside the array bounds.

• Zero-Length Input - When nums is empty, size is zero, the loop body never executes, and the method returns True. This correctly reflects that an empty array trivially satisfies the condition.

Performance Optimizations

The algorithm achieves linear time performance by processing each element exactly once and performing only constant-time work per iteration. The use of the delta array eliminates the need for nested loops or repeated scans to determine when an operation’s effect ends. By updating previous incrementally and subtracting the expired contribution at the moment the window slides, the method avoids recomputing sums over the window, which would be costly for large k. Memory usage is limited to a single auxiliary array of the same size as the input, providing a compact representation of pending adjustments.

Overall, the design balances simplicity with efficiency, delivering a solution that scales well with both the length of nums and the window size k.

Imagine a very long street with a row of houses, and each house has a certain number of colorful balloons tied to its porch. A special machine acts like a giant vacuum that can clean up exactly k houses at once by removing one balloon from each of those houses. The goal is to see if this machine can empty every single house so that not one balloon is left behind.

The code starts by creating a little list to keep track of how many times the machine cleans at each spot as it moves down the street. It walks from the first house to the last one, counting how many balloons are currently at the house. If the machine is working on a group of houses, it remembers those actions as it slides along. At every house, the code looks at the current number of balloons and subtracts the work already done by the machine previously.

If the number of balloons at a house ever drops below zero, it means the machine tried to take away balloons that were not there, which is impossible. Also, if there are still balloons left at a house but the machine does not have enough room left to cover a full group of k houses, the plan will not work. By keeping track of the work done at each step and checking the count of balloons carefully, the code decides if it is possible to clear the entire street successfully.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: linear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster			Java	C++		Python	TS
	WalkCCC			Java	C++		Python
	leetcode.ca			Java	C++	Go	Python	TS
	Progiez			Java	C++		Python
github	charles-wangkai			Java
	everthis		JS
	fsq	Rust
	wisdompeak				C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
Progiez	C++, Java, Python
charles-wangkai	Java
everthis	JavaScript
fsq	Rust
wisdompeak	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality