0054HardArrayStackMonotonic StackRange Minimum/Maximum Query

Largest Cut from a Slate Wall

Tracked in this browser only

Trains the technique from

LeetCode 84Largest Rectangle in Histogram

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def largest_slate_cut(columns: list[int]) -> int:

Java

public int largestSlateCut(int[] columns)

The intended approach

Time O(n)Space O(n)

Every candidate slab is fixed by the shortest column it spans, so it is enough to ask, for each column, how far its own height can reach left and right before meeting something shorter. Keep a stack of column indices whose heights only increase upward. When a column arrives that is no taller than the stack top, that top has met its right wall, and the entry beneath it on the stack is its left wall, so its widest reach is settled and its slab can be scored right then. A closing pass with a height of zero drains whatever is left on the stack. Each index is pushed and popped once.

Pythonentry point: largest_slate_cut

def largest_slate_cut(columns):
    n = len(columns)
    stack = []
    best = 0
    for i in range(n + 1):
        height = 0 if i == n else columns[i]
        while stack and columns[stack[-1]] >= height:
            top = stack.pop()
            left_wall = stack[-1] if stack else -1
            width = i - left_wall - 1
            area = columns[top] * width
            if area > best:
                best = area
        stack.append(i)
    return best

The obvious version

Fix a starting column, walk right one column at a time while tracking the smallest height met so far, and score the slab for each run end. Quadratic, no stack involved.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_largest_slate_cut(columns):
    best = 0
    n = len(columns)
    for start in range(n):
        lowest = columns[start]
        for end in range(start, n):
            if columns[end] < lowest:
                lowest = columns[end]
            area = lowest * (end - start + 1)
            if area > best:
                best = area
    return best

How this problem was checked

Reference solution executed against 12 test cases — 12 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in