Largest Rectangle in Histogram

Loading...LeetCode

Problem

Given an array of integers heights representing the histogram's bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram.

Example 1:

Input: heights = [2,1,5,6,2,3]
Output: 10
Explanation:
The above is a histogram where width of each bar is 1.
The largest rectangle is shown in the red area, which has an area = 10 units.

Example 2:

Input: heights = [2,4]
Output: 4

Pseudocode

- to solve this question
     - need to breakdown the logic of generating largest area
     - easy to be off by one because of look back
     - think of it as, looking for local maxima, neighboring values must be smaller

- using a stack to find the highest histogram
     - push into stack
     - if current height is less than previous height
          - won't be able to generate the largest area
          - look back in the stack until a you find a higher historgram than current
          - calculate area and store Math.max()

Solution

// stack
// https://leetcode.com/problems/largest-rectangle-in-histogram/solutions/425762/javascript-brute-force-and-stack-solutions/
// go through a loop till <= heights.length, including because required to look back
// assess maxArea if current height is less than stack height, keep popping until stack prev height is equal or more than current height
var largestRectangleArea = function (heights) {
  let maxArea = 0;
  const stack = [{ idx: 0, val: 0 }];

  const peek = () => stack[stack.length - 1] || null;

  for (let i = 0; i <= heights.length; i++) {
    const curHeight = heights[i];
    const push = () => stack.push({ idx: i + 1, val: curHeight });

    // console.log("currently traversing:", i);
    // if current height is more than previous stacked value, push
    if (curHeight && curHeight > peek().val) {
      push();
      // console.log(stack);
    } else {
      // if previous height in stack is more than current height, previous height is the top
      // pop it until stack's last value is less than current height
      // calculate maxArea from current index to peek().idx
      while (peek() && peek().val > (curHeight || 0)) {
        // console.log("pop");
        const top = stack.pop();
        const idx = peek() ? peek().idx : 0;
        maxArea = Math.max(maxArea, (i - idx) * top.val);
        // console.log(top, stack, idx, maxArea);
      }

      // once done, push curr height into stack and continue
      push();
    }
  }
  return maxArea;
};

Time and Space Complexity

Time

• What did the code do

• Total -

Space

• What did the code do

• Total -