Leetcode Link: https://leetcode.com/problems/largest-rectangle-in-histogram/
I decided to document this one partially to document some weird quirks in implementations I found, which were not intuitive to me, and also just to think out loud and do some detective work since the only way I really understand one implementation I found was to tear it almost completely apart. I think I know understand it, but I definitely couldn’t come up with it. That said, some of the techniques used in it’s construction may come in handy later on - at the very least, I’d never seen them before.
Essentially I will go through my first failing attempt, cover the recommended neetcode implementation, and then cover a substantially difficult strategy that seems to have the same anatomy at first glance but is, in my eyes considerably less intuitive. That last implementation can be found as the most optimal typescript solution on neetcode - it was also what Claude gave me.
In summary, I think that this did help break open the anatomy of the stack algo. In short, there are three main events when using a stack. The information pushed to the stack at the time of stacking, any mutations that maintain the stack is new information becomes available, and the information at the time where a stack entry is resoled and can be popped off the stack. All of this is obvious, but since the information available at each of these points can be quite different, it has been helpful to view stack algo construction with these 3 parts. Part 2 is pretty optional, and the elite leetcode solution doesn’t partake, while neetcode’s does.
But I will point out, part 1 and 2 are basically mandatory, since a stack you never need to pop isn’t really a stack, and a stack that is never pushed to is also not a stack. Again, these statements are obvious, but I’ve found it’s a nice way to “read” and construct stack algorithms.
Hot top: If you are on leetcode and you are looking at the submission page that shows a bargraph of time-complexity score, you can actually click on the bars. This will bring up the submissions associated with that level of performance.
First attempt
function largestRectangleArea(heights: number[]): number {
const stack: [number, number][] = []
let maxArea = heights[0]
// we have a height for every number leading up to starting height
for (let i = 1; i <= heights[0]; i++){
stack.push([
i, i
])
}
for (let j = 1; j < heights.length; j++){
const height = heights[j]
if (height === 0){
continue
}
while (stack[stack.length-1][0] > height){
stack.pop()
}
// if height is greater than highest height currently recorded
if (height >= stack[stack.length-1][0]){
// then for each previous height, increment volume by it's own heght
for (let i = 0; i < stack.length; i++){
stack[i][1] += stack[i][0]
// check if that volume has surpassed anything
maxArea = Math.max(stack[i][1], maxArea)
}
for (let i = stack[stack.length-1][0] + 1; i <= height; i++){
stack.push([height, height])
}
maxArea = Math.max(height, maxArea)
}
}
return maxArea
};second attempt
function largestRectangleArea(heights: number[]): number {
// Add 0 at the end to handle remaining stack elements
heights.push(0);
const stack: number[] = [-1]; // Initialize with -1 for edge case handling
let maxArea = 0;
for (let i = 0; i < heights.length; i++) {
// While current height is smaller than the last height in stack
while (stack[stack.length - 1] !== -1 &&
heights[i] < heights[stack[stack.length - 1]]) {
// Calculate area with the height of the popped bar
const height = heights[stack.pop()!];
const width = i - stack[stack.length - 1] - 1;
maxArea = Math.max(maxArea, height * width);
}
stack.push(i);
}
// Remove the added 0 to keep input array unchanged
heights.pop();
return maxArea;
}claude answer (also happens to be, I believe, the most performant TS solution on leetcode)
function largestRectangleArea(heights: number[]): number {
// Add 0 at the end to handle remaining stack elements
heights.push(0);
const stack: number[] = [-1]; // Initialize with -1 for edge case handling
let maxArea = 0;
for (let i = 0; i < heights.length; i++) {
// While current height is smaller than the last height in stack
while (stack[stack.length - 1] !== -1 &&
heights[i] < heights[stack[stack.length - 1]]) {
// Calculate area with the height of the popped bar
const height = heights[stack.pop()!];
const width = i - stack[stack.length - 1] - 1;
maxArea = Math.max(maxArea, height * width);
}
stack.push(i);
}
// Remove the added 0 to keep input array unchanged
heights.pop();
return maxArea;
}The claude answer corresponds to the most performant answer on leetcode, but it’s not the most understandable at all. For that, I’d say neetcode’s is, as you’d expect:
class Solution {
/**
* @param {number[]} heights
* @return {number}
*/
largestRectangleArea(heights) {
let maxArea = 0;
const stack = []; // pair: (index, height)
for (let i = 0; i < heights.length; i++) {
let start = i;
while (
stack.length > 0 &&
stack[stack.length - 1][1] > heights[i]
) {
const [index, height] = stack.pop();
maxArea = Math.max(maxArea, height * (i - index));
start = index;
}
stack.push([start, heights[i]]);
}
for (const [index, height] of stack) {
maxArea = Math.max(maxArea, height * (heights.length - index));
}
return maxArea;
}
}It’s a bit more verbose but a lot easier to understand.
The way I think of it, it goes through each vertical height and, as long as that height is monotonically increasing, adds that column to our stack with a height and an index. (technically if you have an index you can always get height, which is where the more performant solution differs.)
Whenever you get a column that’s smaller than any of the heights recorded on that stack, you pop them all off and calculate their total area as you go.
I think about it this way - you could
- try to calculate ahead (for a cost of additional time complexity) for each height
- calculate as you go along (I tried this and I think it would work but it’s a lot of extra work since the third option exists)
- calculate whenever the area of a certain height ends because a new height has arrived and its shorter than the previous height(s).
This last approach I think fits the best with the philosophy of using stacks itself. The second one reminds me more of sliding windows, and may not play well with stacks, whereas the first is really just brute force with O(n2) time complexity, which would work but would not impress an interviewer.
I say that approach #3 is so inline with the philosophy of stacks because stacks work the best when you are recording info to process later once you have its full context. That’s exactly what we’re doing here. We are saying “hey okay, this new height might be the start of a rectangle with the largest maxHeight. I’m going to save the information I have now, like the height and starting index, and then I will wait for a future event when I have the information to know when the rectangle ends. I will see if it has the maxArea then.”
Stacks are a useful approach to say hey, this stuff still needs to be processed, then once its processed, get it out of there.
There’s a twist to this, but it’s not really a twist at all. We just need to remember, in this use of stacks, we are updating info of a particular height only twice. Once when we initially add it to the stack, and another time when we pop it from the stack.
A few expectations follow from this -
- every item will be pushed to the stack
- every item will eventually be popped from the stack
To achieve the second condition, neetcode explicitly creates a forloop to do this.
There is also a simpler way that we can do that I borrowed from Claude’s answer, which is to just add a 0 to the end of heights and the shape of our ingested data to our advantage.
Most of the reason I actually started writing these notes though was because this single line claude’s answer / the most performant solution on Leetcode was a total mindfuck to me.
const width = i - stack[stack.length - 1] - 1;After pondering this line for a while, I realized something that simply wasn’t intuitive to me right away -
because in this solution, the stack is being pop()’d before they calculate the width, they need to get a width that’s just 1 narrower than the post-pop() stack. If they just popped before, i - stack[-1] (to use python syntax for brevity) would provide the proper width.
Take the example where these are our heights:
1, 2, 3, 4, 1
So that by the time we’ve saved the height for index 3 (which has height 4), we have a stack that looks like this:
| start index | height |
|---|---|
| 0 | 1 |
| 1 | 2 |
| 2 | 3 |
| 3 | 4 |
At this point we check to see if the last item of the stack is greater than the next height in the list, and it is - 4 is greater than 1. |
So if we just subtracted the last start index value of our stack, which is 3 from our current index of 4, we’d get 1, which is exactly the width we want for the column with height 4 that only occurs over a distance of 1.
3 is also greater than one, so we do the same for 3 - we subtract it’s start index of 2 from our current index of 4 and we get 2, which is also right - the rectangle starting at 3 has a width of 2.
We do pretty much the same thing for the stack entry at start index: 2, and we get a width of 3.
The thing is, in the Claude example, they pop first, so to get the same result, they need to subtract one from the last index in the stack.
The reason I needed to write this down is just because the math here, though simple, really confused me. What was counterintuitive was the idea of subtracting one from the difference to compensate for a starting index that was one too low.
The I finally realized than a starting index that was one too low would actually lead to a higher value for the difference. I.e, if we have 1, 2, 1 and we’re considering the last height at index 2 and we pop [1, 2] off our stack, the next item on the stack is [0, 1. If we subtract 0 from our index of 2, we get 2 for the width of the 2 height column. But that’s not right - the 2 column is only there for a width of one. And this is because, having popped it, our starting index is too low by one.
To re-iterate just one more time, what was confusing for me was just how decreasing the value of the bottom of a range by actually increments the span of that range, not decrements. Somehow that was counterintuitive to me when I just just looking at numbers.
There are still a lot of things about the Claude solution that don’t make sense to me though.
- Why, when I get rid of this sort of backwards
1-stack[-1]-1by puttingpopafter width calculation, does this algo fail on the2, 1, 2testcase? - How does this algo handling the backwards
start-indexchecking like neetcode’s algo does? - How does this algo handle duplicates in the past, like in
1, 2, 1?
The best way to figure this out seems to be to go through the test case, which happens to be pretty short. Just to be clear, here’s what I changed Claude’s algo to:
function largestRectangleArea(heights: number[]): number {
heights.push(0);
const stack: number[] = [-1];
let maxArea = 0;
for (let i = 0; i < heights.length; i++) {
while (
stack[stack.length - 1] !== -1 &&
heights[i] < heights[stack[stack.length - 1]]
) {
const width = i - stack[stack.length - 1];
const height = heights[stack.pop()!];
maxArea = Math.max(maxArea, height * width);
}
stack.push(i);
}
return maxArea;
}See? I’ve put the pop statement after width calculation, and removed the -1 addendum to the width calculation line. And this is correct for 53/99 test-cases, so it’s probably right for most of the more obvious cases, which means our odds for this very simple case showing us what is breaking it are good.
Okay so I tried it out, and it turns out that this algo must do the backwards stack computation in some different way that I’ve disrupted. We get that 1 continues through the second 2, but not that a rectangle with a height of 1 starts at the first 2 as well.
That’s why we get this wrong answer 2 instead of the expected 3. But why do we get 3 when the popping happens earlier?
So here’s the one with some things shuffled around so all test cases pass:
Let’s check it out. Oh also make note, that if we are getting -1 on that width line, we’re actually subtracting -1, which is adding one. So right after popping that first 2, we do 1+1-1 to get a width of 1. Perfect.
Fuck. I followed it all the way through and it doesn’t make much more sense to me to be honest. It works so well, but I don’t get it. We pop off that last 2, and from our vantage point of i = 3, we do 3 - 1 - 1 and get 1.
Cool. We would be doing 3 - 2 to get one, which would work fine, but of course we’re popping that 2 entry off first, so the previous index is just 1. So we get the difference between 3 and 1 and it’s 2, but we subtract an extra 1 from that to make it non-inclusive of the bottom delimiting index, which we don’t want to include since it’s not actually where the rectangle starts.
Now what happens for the 1 on the stack on the phase of the while loop that we pop it off?
I think what happens is this -
imagine that we had something more like 1, 3, 2, 3. When we go to the second 1, the initial 2 would get popped off, leaving the last index before it to be a 0. This means that when we pop off the 3 and then the 2 at the end, we check to see where the 2 began. We know it ends at i, which is 4, cool. But where does it start? Well it start it at the space in front of 0 - 0 of course is not where it starts, there’s a 1 there. But we know that because that’s the last index with a LOWER value than 2, if we subtract the index just after that first lower value in the past from our current index (which we know is a HIGHER value than 2, and is so in a monotonic way, ensuring no breaks in 2 up to that point) then we will get the width of that 2.
So there’s some logic there that makes sense. We pop first and then, instead of doing neetcode’s method of keeping our first index up to date as we pop bigger values that we can extend our lower values back into, we pop first, and we know that our current rectangle starts just after the new end of our stack, which now points to the first value going backwards that cannot be part of our rectangle.
We’re really finding these two discrete pieces of information - given a current index, what is the first position going backwards that can’t be in our rectangle?
answer: the one right before the value we just popped.
explanation: because we have enforced that our stack is monotonically ascending and there are no duplicates either, we know that our rectangle for any given value will always start just after the first value on the stack that is lower than it. And since we popped it, the first value lower than it is always going to be at the top of the stack.
This includes our -1 sentinel value! i-(-1)-1 is always going to equal i - the -1 is a way to mathematically say that our current value goes all the way to the beginning, in very much the same way that if our value’s first instance was at index 0, well, that would get popped too, since if it has a height of anything other than 0, that last 0 value we push is going to pop that off and put us back at -1.
Geez. Yeah the logic of this is so strange. It does make sense, but it’s really twisted.
I pretty much handled this in the previous exploration. Backwards values are handled by you know, popping the current value and just getting the index of one in front of the last value on the stack, which is going to be the first index that we can’t include in our current rectangle as I feel I’ve now stated at least 4 times because it’s really hard to get into words. I think it should probably be a picture.
So let’s consider the case of 1, 2, 1. What I’m curious about is, since our stack really becomes 1, 2, 1, 0, once we get to that 0 and we pop off 1, what happens then?
Well before that, we’ll have already popped off 2 once we’ve gotten to i=2. So let’s jump there.
Okay! The explanation is really simple actually!
The backwards-computation works as demonstrated thoroughly - once we pop the current height we’re considering, we end up starting our rectangle just after the last documented index. OR -1 , which effectively allows us to just compute our width as being equivalent to i.
THE KICKER IS, with redundant values, we compute all duplicate heights in our stack, even if intermediate values like the 2 here have already been popped away leaving us with a stack where the heights pointed to by our indexes are -, 1, 1. From those repeats, an incomplete computation of the width of the first 1 is created, which extends only back into the 2 before it. But then, the other i’s width is computed to. This one correctly extends back to the index just after -1, which would be 0, and just like the first one, also correctly extends to our current i of 3. So we get a width of 3! The first 1’s width is half right, but doesn’t go back far enough, even if it ends in the right place. The second 1’s width is fully right. It starts and ends in the right place. It does make you think, since the second 1’s width is, in this case, useless, we might optimize by not calculating it at all.
So I guess this all makes sense now. Is it intuitive? Eh. A little more so. Still a crazy way to do this, what with the -1 sentinel value, the clever 0 put at the end of height. Although doing away with the backwards computation/mutation that neetcode does is pretty smart, and it allows us to compute the width at pop-time without doing any maintenance, which is cool.