Largest Rectangle in Histogram

LeetCode Q 84 - Largest Rectangle in Histogram

Given n non-negative integers representing the histogram’s bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

The largest rectangle is shown in the shaded area, which has area = 10 unit.

Example: Input: [2,1,5,6,2,3] ; Output: 10

Solution

Code

public int largestRectangleArea(int[] heights) {
  if (heights == null || heights.length == 0) return 0;

  int len = heights.length
  int[] lessFromLeft = new int[len]; //idx of the first bar on the left whose height is lower than current 
  int[] lessFromRight = new int[len]; //idx of the first bar on the right whose height is lower than current

  // find PSE
  lessFromLeft[0] = -1;
  for (int i = 1; i < len; i++) {
    int index = i - 1;
    while (index >= 0 && heights[index] >= heights[i])
      index = lessFromLeft[index];
    lessFromLeft[i] = index;
  }

  // find NSE
  lessFromRight[len - 1] = len;
  for (int i = len - 2; i >= 0; i--) {
    int index = i + 1;
    while (index < len && heights[index] >= heights[i])
      index = lessFromRight[index];
    lessFromRight[i] = index;
  }

  int maxArea = 0;
  for (int i = 0; i < len; i++) 
    maxArea = Math.max(maxArea, heights[i] * (lessFromRight[i] - lessFromLeft[i]));

  return maxArea;
}