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. 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. Using i prevents previous 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
}