Largest Rectangle in Histogram

This page explains Java solution to problem Largest Rectangle in Histogram using Stack data structure.

Problem Statement

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.

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

Input:

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

Output:

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

Solution

package com.vc.hard;

import java.util.Stack;

class LargestRectangleInHistogram {
    public int largestRectangleArea(int[] heights) {
        Stack<Integer> st = new Stack<>();
        st.push(-1);
        int maxHeight = 0;
        for(int i = 0; i < heights.length; i++) {
            while(st.peek() != -1 && heights[st.peek()] > heights[i]) {
                maxHeight = Math.max(maxHeight, heights[st.pop()] * (i - st.peek() - 1));
            }
            st.push(i);
        }
        while(st.peek() != -1) {
            maxHeight = Math.max(maxHeight, heights[st.pop()] * (heights.length - st.peek() - 1));
        }
        return maxHeight;
    }
}

Time Complexity

O(N) Where
N is number of elements in input array

Space Complexity

O(N)