Largest Rectangle in Histogram
Real-world version: Largest Cut from a Slate WallThe statement here is our own: the same inputs, outputs and technique.
A quarry face is stored as columns, where columns[i] is how many square slate tiles are stacked in the i-th column. Every column is one tile wide, columns touch with no gap, and all of them rest on the same floor. A column may hold no tiles at all.
A cutter can lift out one rectangular slab. The slab has to span a run of neighbouring columns and sit flush on the floor, so its height can never exceed the shortest column it spans, and its width is the number of columns in the run.
Report the tile count of the biggest slab the cutter can lift, that is the largest value of run width times the smallest column height inside the run. If no column holds a tile, the answer is 0.
Examples
Example 1
- Input
- columns = [3, 6, 5, 8, 4]
- Output
- 16
Spanning the last four columns caps the height at 4 tiles, giving 4 by 4. Nothing else reaches 16: the single tallest column only yields 8, and taking all five columns caps the height at 3 for a total of 15.
Example 2
- Input
- columns = [5, 5]
- Output
- 10
Both columns are the same height, so the slab covers the whole face without wasting any height.
Example 3
- Input
- columns = [0, 0]
- Output
- 0
The face is bare, so every run has a shortest height of zero and no slab can be lifted.
Constraints
- 1 <= columns.length <= 10^5
- 0 <= columns[i] <= 10^4
The signature
The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.
def largest_slate_cut(columns: list[int]) -> int:public int largestSlateCut(int[] columns)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 12 test cases: 12 passed
- Passed: 3 worked examples confirmed by running the code
- Passed: 0 eight-word sequences shared with the parent problem's text
- Passed: Agrees with an independent brute-force solution on random inputs
- Passed: Test set shown to catch deliberately broken solutions
- Passed: Reviewed by a separate quality pass
- Passed: Function arity matches the parent problem's