Largest Rectangle IN Histogram

Problem

Given an integer array heights representing the heights of histogram bars, write a function to find the largest rectangular area possible in a histogram, where each bar’s width is 1.

Input:

heights = [2,8,5,6,2,3]

Output:

15

Explanation

To solve this question, we calculate the largest rectangle that contains the bar at each index of the array, and return the largest of those rectangles at the end. By using a monotonically increasing stack, we can solve this question in O(n) time complexity, compared to the brute-force solution which takes O(n2) time.

Largest Rectangle at each Index

To calculate the largest rectangle at each index, we need to know the index of the first shorter bar to both the left and the right of the current bar. The width of the rectangle is the difference between the two indices - 1, and the height is the height of the current bar.

Brute-Force Solution

The brute-force solution iterates over each bar in the array, and for each bar, finds the first shortest bar to the left and the right of the bar using two while loops, for a time complexity of O(n2).

def largest_rectangle_area(heights):
  stack = []
  max_area = 0
  i = 0
  while i < len(heights):
    if not stack or heights[i] >= heights[stack[-1]]:
      stack.append(i)
      i += 1
    else:
      top = stack.pop()
      right = i - 1
      left = stack[-1] if stack else -1
      area = heights[top] * (right - left)
      max_area = max(max_area, area)

  while stack:
    top = stack.pop()
    width = i - stack[-1] - 1 if stack else i
    area = heights[top] * width
    max_area = max(max_area, area)
  return max_area

public int largestRectangleArea(int[] heights) {
    Stack<Integer> stack = new Stack<>();
    int maxArea = 0;
    int i = 0;
    while (i < heights.length) {
        if (stack.isEmpty() || heights[i] >= heights[stack.peek()]) {
            stack.push(i);
            i++;
        } else {
            int top = stack.pop();
            int right = i - 1;
            int left = stack.isEmpty() ? -1 : stack.peek();
            int area = heights[top] * (right - left);
            maxArea = Math.max(maxArea, area);
        }
    }

    while (!stack.isEmpty()) {
        int top = stack.pop();
        int width = stack.isEmpty() ? i : i - stack.peek() - 1;
        int area = heights[top] * width;
        maxArea = Math.max(maxArea, area);
    }
    return maxArea;
}

func largestRectangleArea(heights []int) int {
    stack := []int{}
    maxArea := 0
    i := 0
    for i < len(heights) {
        if len(stack) == 0 || heights[i] >= heights[stack[len(stack)-1]] {
            stack = append(stack, i)
            i++
        } else {
            top := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            right := i - 1
            left := -1
            if len(stack) > 0 {
                left = stack[len(stack)-1]
            }
            area := heights[top] * (right - left)
            if area > maxArea {
                maxArea = area
            }
        }
    }

    for len(stack) > 0 {
        top := stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        width := i
        if len(stack) > 0 {
            width = i - stack[len(stack)-1] - 1
        }
        area := heights[top] * width
        if area > maxArea {
            maxArea = area
        }
    }
    return maxArea
}

function largestRectangleArea(heights: number[]): number {
  let stack: number[] = [];
  let maxArea: number = 0;
  let i: number = 0;
  while (i < heights.length) {
    if (stack.length === 0 || heights[i] >= heights[stack[stack.length - 1]]) {
      stack.push(i);
      i++;
    } else {
      let top: number = stack.pop()!;
      let right: number = i - 1;
      let left: number = stack.length === 0 ? -1 : stack[stack.length - 1];
      let area: number = heights[top] * (right - left);
      maxArea = Math.max(maxArea, area);
    }
  }

  while (stack.length > 0) {
    let top: number = stack.pop()!;
    let width: number = stack.length === 0 ? i : i - stack[stack.length - 1] - 1;
    let area: number = heights[top] * width;
    maxArea = Math.max(maxArea, area);
  }
  return maxArea;
}

Monotonically Increasing Stack

By using a monotonically increasing stack, we can find the first shortest bar to the left and right of each bar in O(n) time complexity.

We first initialize our stack, as well as a variable to store the maximum area and a pointer i to iterate over the array. The stack contains the indices of the bars in increasing order of their heights. When an index is placed on the stack, it means we are waiting to find a shorter bar to the right of that current index.

We then iterate over the array. If height[i] is greater than the height of the index at the top of the stack, we push i onto the stack. If i is less than the height of index at the top of the stack, we pop the index at the top of the stack and calculate the area of the rectangle containing that index.

Pushing to the Stack

If height[i] is greater than the height of the index at the top of the stack (or if the stack is currently empty), we push i onto the stack. This means we are waiting to find a shorter bar to the right of i, and we increment i.

Popping from the Stack

If height[i] is less than the height of the index at the top of the stack, we have enough information to calculate the area of the rectangle containing the index at the top of the stack. i is the first shorter bar to the right of the index at the top of the stack. Because the stack is monotonically increasing, the index beneath the index at the top is the first shorter bar to the left of it (or -1 if the stack is empty).

i still has the potential to be the right boundary for the new index at the top of the stack after the previous index was popped, so we don’t increment i, and instead, move to the next iteration.

Emptying the Stack

When i has iterated over the entire array, we still need to process the remaining indexes on the stack, which are the indexes that have not yet found a shorter bar to the right. So to calculate the area of the rectangle for these indexes, we use the end of the array as the right boundary, while the calculation for the left boundary remains the same.

When the stack is empty, we have processed all the indexes, and we return the maximum area.

Solution