Ctrl K

Flatten With a Sliding Press

Medium
Stacks of blocks stand in a row; their heights are given in heights. A press of width width comes down on width **adjacent** stacks at a time and removes exactly one block from each of them. You may press as often as you like, but the press must fit entirely inside the row, and it cannot come down on a stack of height 0 (heights never go negative). Return True if every block can be removed, making all heights zero, and False otherwise.
Example 1
heights=[1, 3, 2, 0], width=2 → True

Column 0 can only be lowered by pressing [0, 1], which gives [0, 2, 2, 0]. Pressing [1, 2] twice flattens everything.

Example 2
heights=[2, 1, 2], width=2 → False

Zeroing column 0 needs two presses on [0, 1], but column 1 would drop below zero.

Example 3
heights=[4, 0, 7], width=1 → True

A press of width 1 lowers any single column, so flattening always works.

Constraints
  • 1 ≤ width ≤ len(heights) ≤ 10⁵
  • 0 ≤ heights[i] ≤ 10⁶
Have you seen this problem in a real interview?
Solved by0
Tried by0
Submissions0
Acceptance—
Topics
Similar problemsShortest Stretch to the Goal MediumProduct of All the Others MediumStudios for Recording Sessions MediumLongest Run with a Given Sum MediumBatch of Segment Adjustments Medium
loading Python…
Input
heights=[1, 3, 2, 0], width=2
Expected
True

Run checks the first 3 tests in your browser. Submit checks all 104 tests on the server, hidden ones included.