LC 84. Largest Rectangle in Histogram

The problem

Solution

Largest Rectangle in Histogram is my first LC hard problem, and the trick with calculating the width lives up to that difficulty. I came across this problem while working with monotonic stacks so I had practiced the relevant patterns but had to watch a tutorial after failing test cases. I calculated the area for cases of vertical rectangles (2 histograms wide), but didn't handle more horizontal ones leading to failures.

From comments and other examples, I learned that by using a monotonically increasing stack, all widths can be handled by subtracting the current index from each of the popped histogram indices. With that, a new area is calculated and set as the answer if greater than the previous one. Another important trick is to run the loop an extra time with the height as 0 to include the final monotonic stack's values.

Lastly, the trickiest part of this problem was the width calculation due to the implicit logic involved. At first, it seemed more intuitive to calculate the width using i - idx, the difference between the current and popped indices. The stack[stack.length - 1] - 1 in the width calculation represents the previous lowest index encountered, excluding the previous min itself. However, when a higher number is popped later on in the sequence, that minimum's width must span from the current index all the way back to the next lowest height. For example, consider [3, 1, 5, 6, 2, 3]. On the final iteration of the for loop, i = 6 (hardcoded to always be height = 0), every value will be popped that is greater than 0. When the 2 is popped, the width needs to span from the end back to the previous minimum for an area of 8. This is directly achieved by using the previous minimum of 1's index from the stack.

Next, notice that the width is defined using a ternary where the second case is the one most people would think of immediately (the current index - the starting index). However, when the stack is empty, the current length, i, is used no matter where the stack's index is. The stack being empty implies that the current height is the lowest value encountered thus far. Therefore, the entire length of the array up to the current index can be assumed as the width.

Consider the test case [2, 1, 2] when i === nums.length, the last iteration. The stack will empty for the final time on the index for 1 and should calculate 3 as the answer. Using i - stack[stack.length - 1] - 1 (current index - starting index) will incorrectly return 2 as the width because the first 2 was popped when the the loop hit height 1. Using i prevents previous popped values that are greater than the current height from being ignored.

function largestRectangleArea(heights: number[]): number {
  let answer = 0
  let stack = []
  for (let i = 0; i <= heights.length; i++) {
    let current = heights[i] || 0
    while (stack.length && current < heights[stack[stack.length - 1]]) {
      let idx = stack.pop()
      let height = heights[idx]
      let width = !stack.length ? i : i - stack[stack.length - 1] - 1
      answer = Math.max(answer, height * width)
    }
    stack.push(i)
  }
  return answer
}