# 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.

Example 1:

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

If you have any suggestions in below code, please create a pull request by clicking here.
``````
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

O(N)