Problem overview
The method largestRectangleArea receives an array heights. Each number is the height of one bar in a histogram, and every bar is 1 unit wide, with the bars side by side. The method returns the area of the largest rectangle that fits inside the histogram. The rectangle must be made of whole neighbouring bars, and its height can't go above the shortest bar it covers.
For heights = [2, 1, 5, 6, 2, 3] the answer is 10. The bars 5 and 6 are both at least 5 tall, so a rectangle of height 5 and width 2 fits over them, giving 10. For [2, 4] the answer is 4: either the bar 4 alone (area 4), or both bars at height 2 (also 4). The statement allows up to 100,000 bars, so the solution needs to be close to linear.
Approach: every bar as the shortest bar of its rectangle
A trying-everything solution picks every pair of start and end bars, finds the lowest bar between them and computes the area: O(n³), or O(n²) when the minimum is tracked while the end moves right. With 100,000 bars that is far too slow.
The lesson uses a different way to look at it. The best rectangle has a shortest bar, and its height is exactly that bar's height. So try each bar i as that shortest bar. The widest rectangle of height heights[i] stretches left and right until it meets a bar that is lower than heights[i]. If left[i] is the index of the nearest lower bar on the left, and right[i] the nearest lower bar on the right, the rectangle covers the bars strictly between them, which is right[i] - left[i] - 1 bars wide. Its area is heights[i] * (right[i] - left[i] - 1). The answer is the maximum of that over all bars.
That leaves one job: finding left and right for every bar quickly. A stack does it in one pass per direction. Scanning from left to right, the stack holds indices of bars still waiting to meet a lower bar to their right, and their heights never decrease from bottom to top. When a bar i arrives, it is lower than every waiting bar taller than it, so it is the nearest lower bar on the right for all of them: pop each of those, write i into right, and push i. A second pass from right to left, with the same logic, finds left.
When there is no lower bar, the code uses sentinel values: -1 for left and n for right, as if a bar of height 0 stood just outside each end. For the first bar of [2, 4] that gives left = -1, right = 2, a width of 2 and an area of 4.
Step by step
- Store the length in
n, a number, since many steps use it. - Create
leftwithnew Array(n)andfill(-1). The value-1means "no lower bar on the left". - Create
rightthe same way, filled withn, which is one past the last valid index and so can't be mistaken for a real bar. - Create the stack, an empty
number[], for indices of bars waiting for their lower neighbour. - Scan from left to right with
ifrom 0 ton - 1. - Call the helper as
this.removeAndUpdate(heights, stack, right, i). Scanning rightwards, the first lower bar an index meets is its nearest lower bar on the right, sorightis the array to fill. - Reset the stack with
stack = []. Indices left over in the first pass keepright = n. This requiresletrather thanconst. - Scan from right to left, with
ifromn - 1down to 0. The condition isi >= 0so that index 0 is included. - Call the helper again, this time with
left. The helper doesn't know the direction. It only comparesheights[i]with the bars on the stack. - Declare
answeras 0. Areas are never negative. - Loop over every bar once more, trying each one as the shortest bar.
- Update the answer with
Math.max(answer, heights[i] * (right[i] - left[i] - 1)). The subtraction of 1 removes the two bounding bars from the count. - Return
answer. - Write the helper as a method
removeAndUpdate, placed abovelargestRectangleAreain the class. It takesheights,stack,arrandiand returnsvoid. The arrayarris whichever ofleftorrightthe caller passes. - Pop the taller bars. A
whileloop runs while the stack isn't empty andheights[i]is less than the height of the bar on top. The emptiness test comes first. - Record
iinarrat the top index, thenpopit. - Push
i. Only strictly taller bars were popped, so bars equal toheights[i]stay on the stack, and the heights still never decrease.
The solution in TypeScript
class Solution {
removeAndUpdate(heights: number[], stack: number[], arr: number[], i: number): void {
while (stack.length > 0 && heights[i] < heights[stack[stack.length - 1]]) {
arr[stack[stack.length - 1]] = i;
stack.pop();
}
stack.push(i);
}
largestRectangleArea(heights: number[]): number {
let n: number = heights.length;
let left: number[] = new Array(n).fill(-1);
let right: number[] = new Array(n).fill(n);
let stack: number[] = [];
for (let i = 0; i < n; i++) {
this.removeAndUpdate(heights, stack, right, i);
}
stack = [];
for (let i = n - 1; i >= 0; i--) {
this.removeAndUpdate(heights, stack, left, i);
}
let answer: number = 0;
for (let i = 0; i < n; i++) {
answer = Math.max(answer, heights[i] * (right[i] - left[i] - 1));
}
return answer;
}
}
The TypeScript details worth a closer look:
- Methods call each other through
this.removeAndUpdatebelongs to the class, so the other method calls it asthis.removeAndUpdate(...). Writing the bare name would look for a variable of that name and fail. - Arrays are passed by reference. The helper changes
stackandarrdirectly, and the caller sees those changes. That is how it fillsleftandrightwithout returning anything, which is why its return type isvoid. stack = []needslet. Aconstvariable can't be reassigned. Another option isstack.length = 0, which empties the same array.new Array(n).fill(v).new Array(n)alone makes empty slots, andfillsets every slot tov.- The same helper for both directions. Scanning right to left, "the nearest lower bar met first" is the nearest on the left, so passing
leftasarris all that changes. - Numbers are doubles. The largest possible area here, 100,000 bars of height 10,000, is 1,000,000,000, far below the point where integers lose exactness, so there is no overflow to worry about.
Complexity
Time: O(n). Each of the two passes pushes every index once and pops it at most once, so each pass costs O(n) in total despite the while loop. The final loop is O(n) too.
Space: O(n). The arrays left and right hold n numbers each, and the stack holds at most n indices.
Edge cases and common mistakes
- One bar.
[3]givesleft = [-1]andright = [1], a width of 1 and an area of 3. - Equal bars.
[3, 3, 3]gives 9. Equal bars aren't popped by each other, so no bar treats an equal neighbour as a boundary, and each reaches both ends. - A bar of height 0.
[0]gives 0. In[2, 0, 2]the zero splits the histogram, because a rectangle can't pass through it, so the answer is 2. - Increasing heights.
[1, 2, 3, 4]gives 6, from the bars 3 and 4 at height 3 or the bars 2, 3 and 4 at height 2. - Using
<=instead of<in the helper. Popping equal bars would end the rectangle early at the first equal neighbour, and it would give a smaller width for[3, 3, 3]. - Forgetting to reset the stack. Starting the second pass with the leftovers of the first corrupts
left. - Not subtracting 1 from the width.
right[i] - left[i]counts one bar too many, because the bounding bars aren't part of the rectangle. - Checking the top before the emptiness test. Reading
stack[stack.length - 1]on an empty stack givesundefined, and comparing with it is always false, which hides the mistake instead of reporting it.
Testing
[2, 1, 5, 6, 2, 3]gives10.[2, 4]gives4.[3, 3, 3]gives9.[1, 2, 3, 4]gives6.[0]gives0.