Mural on the Stepped Wall
A school courtyard has an old garden wall built from columns of bricks, each column one brick wide, standing side by side with no gaps between them. Over the years some columns lost bricks, so the top of the wall is a jagged staircase. A column with height 0 has lost all its bricks.
The art class wants to paint the biggest possible rectangular mural on the wall. The rectangle must sit on the ground, cover whole columns side by side, and stay on bricks: it cannot rise above the shortest column it spans.
Your task
Write largestMural(heights). heights[i] is the number of bricks in column i, and each brick is 1 × 1. Return the largest area, in bricks, of a rectangle that spans one or more consecutive columns and is no taller than the shortest of them.
Return 0 for an empty wall or a wall with no bricks at all.
largestMural(heights: int[]) → int
Examples
heights = [3, 5, 4, 1, 6, 2]
9
Columns 0 to 2 (heights 3, 5, 4) are all at least 3 tall, giving 3 × 3 = 9. The tallest column alone gives only 6, and columns 1 and 2 give 4 × 2 = 8. Any rectangle that includes column 3 is at most 1 brick tall: 1 × 6 = 6.
heights = [2, 4, 4, 0, 5]
8
Columns 1 and 2 give 4 × 2 = 8. Column 3 has no bricks, so no rectangle can cross it, and the 5 on its own is only 5.
Constraints
- 0 ≤ heights.length ≤ 100,000
- 0 ≤ heights[i] ≤ 10,000
Start with brute force
Try every pair of start and end columns, keep a running minimum height as the end moves right, and compute minimum × width.
That is O(n²): about 5 billion pairs for a wall of 100,000 columns. Most of the work is wasted because a run of columns is rechecked from every starting point. The insight is that each column only needs to know where it is blocked on each side.
Hints
0 of 4 shown- Hint 1
Fix one column, say the 4 in
[3, 5, 4, 1, 6, 2], and say the mural must be exactly as tall as that column. How far left and right can the mural stretch? - Hint 2
Every best mural is exactly as tall as its shortest column. So for each column, you want the widest rectangle of that column's height: it stretches until it hits a shorter column on each side. The answer is the best of these n candidates.
- Hint 3
So for each column you need the nearest shorter column on the left and on the right. That is a "next smaller" question, which a stack of columns with increasing heights answers in one pass.
- Hint 4
Walk left to right with a stack of indexes whose heights increase. When column
iis shorter than the top, pop the top:iis its right limit, and the new top of the stack (or -1 if empty) is its left limit, so its area isheight × (i - left - 1). Pushi. At the end, treat one extra column of height 0 to pop everything left.
Walkthrough and solution
Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.
How to solve it
The best mural is as tall as its shortest column. So try each column as "the shortest": its mural spreads sideways until it meets a shorter column on each side. A stack of increasing heights finds both limits. When a shorter column arrives and pops a column off the stack, that newcomer is the popped column's right limit, and the column now below it on the stack is its left limit.
Trace [3, 5, 4, 1, 6, 2] (stack shown as index(height)):
- i = 0, 1: heights 3 and 5 keep increasing. Push both. Stack: 0(3), 1(5).
- i = 2 (4). 5 ≥ 4: pop 1. Left limit 0, right limit 2, width 1. Area 5 × 1 = 5. Push. Stack: 0(3), 2(4).
- i = 3 (1). Pop 2: left 0, width 3 - 0 - 1 = 2, area 4 × 2 = 8. Pop 0: stack empty so left = -1, width 3, area 3 × 3 = 9. Push. Stack: 3(1).
- i = 4 (6). Push. Stack: 3(1), 4(6).
- i = 5 (2). Pop 4: left 3, width 1, area 6. Push. Stack: 3(1), 5(2).
- i = 6, the extra 0. Pop 5: left 3, width 2, area 4. Pop 3: left -1, width 6, area 6.
The best area seen is 9. Two details matter. The final height-0 step flushes columns that never met a shorter one. And when a column is popped, the area uses the index below it on the stack, not its own index, because every column between them was taller and already popped.
function largestMural(heights) {
const stack = []; // indexes; heights increase from bottom to top
let best = 0;
for (let i = 0; i <= heights.length; i++) {
const h = i < heights.length ? heights[i] : 0; // a final 0 flushes the stack
while (stack.length > 0 && heights[stack[stack.length - 1]] >= h) {
const top = stack.pop();
// shorter neighbours: left is the new top, right is i
const left = stack.length > 0 ? stack[stack.length - 1] : -1;
best = Math.max(best, heights[top] * (i - left - 1));
}
stack.push(i);
}
return best;
}def largest_mural(heights):
stack = [] # indexes; heights increase from bottom to top
best = 0
for i in range(len(heights) + 1):
h = heights[i] if i < len(heights) else 0 # a final 0 flushes the stack
while stack and heights[stack[-1]] >= h:
top = stack.pop()
# shorter neighbours: left is the new top, right is i
left = stack[-1] if stack else -1
best = max(best, heights[top] * (i - left - 1))
stack.append(i)
return bestRun your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.