737. Can k at a Time Empty It

One operation picks k CONSECUTIVE positions and subtracts 1 from each. Print yes if some sequence of operations makes every value exactly 0, and no otherwise. Values never need to go negative, and an operation that would take any value below 0 is not allowed.

2 2 3 1 1 0, k = 3 -> yes 1 3 1 1, k = 2 -> no 2 1, k = 2 -> no 1 1, k = 2 -> yes

## The leftmost position has no choice

Position 1 can only be reduced by operations that START at position 1, because any operation starting further right does not reach it. So the number of operations starting at position 1 is forced: it is exactly a[1].

Apply them, and now position 2 is in the same situation. The whole sequence is forced, with no decision anywhere, which is what makes a single left-to-right pass a proof and not a heuristic.

That is the same argument problem 707 uses for its flips, and problem 724 uses for its range increments. Three problems, one structure: the leftmost unsatisfied position determines the next move uniquely.

## Carrying the operations cheaply

Applying each forced operation across its k positions is O(n k). Instead carry a running count of operations still in force, and a difference array recording where each batch stops:

cur = 0 for i in 1 .. n: cur += d[i] # batches that expire here leave need = a[i] - cur # what is still required at i if need == 0: continue if need < 0: return no # already pushed below zero if i + k - 1 > n: return no # no room for an operation starting here cur += need d[i + k] -= need return yes

cur is how much has already been subtracted from the current position by operations started earlier and still covering it.

## The two ways to fail, and they are different

`need < 0` means earlier forced operations have already subtracted more than this position holds. Nothing can undo that, because operations only subtract. 2 1 with k = 2 fails here: the two operations forced by position 1 drive position 2 to -1.

`i + k - 1 > n` means a positive amount remains but no operation starting here fits inside the array. 0 2 with k = 2 is the smallest case: position 1 needs nothing, then position 2 still holds 2 and an operation starting there would run off the end. 1 2 3 4 with k = 2 is the same failure further in, reaching position 4 with 2 still to remove and i + k - 1 = 5.

Both are real and an implementation that checks only one passes a surprising number of tests. Read the branch a failing case actually takes before treating it as a witness for one of them: 1 3 1 1 with k = 2 looks like it should run out of room, but it never gets that far. It exits on need < 0 at position 3, exactly like 2 1, because the two operations forced at position 2 also cover position 3, which only holds 1.

## Why the total being divisible by k is not enough

Every operation removes exactly k from the total, so a solvable array has a total divisible by k. That is necessary and NOT sufficient: 2 1 totals 3 and k = 2 does not divide it, but 1 3 1 1 totals 6 which k = 2 divides cleanly, and it is still impossible.

Checking divisibility and stopping there is the trap this problem is built around.

## Boundaries

An all-zero array answers yes for any k. k = 1 always answers yes, because every position can be emptied independently. k = n answers yes exactly when all values are equal.

## Cost

Time O(n). Space O(n).

Constraints - `1 ≤ k ≤ n ≤ 200000` - `0 ≤ each value ≤ 10^9`