Working Java Program For Largest Rectangle in Histogram

Problem:
An array of integers A is given of size N. A represents a histogram i.e A[i] denotes height of the ith histogram’s bar. Width of each bar is 1.

This is a question you will find in LeetCode or InterviewBit and asked in interviews of Google, Amazon or Facebook.


Above you can see  a histogram with different heights. Below the largest area has been highlighted.

For implementing we have used a stack. Stack will contain index of the array in ascending order of values.

Idea is we are going to calculate largest area for each bar & then take the maximum out of them. For a bar, the max area would start after the left bar where the value is less than the current bar. Area will end when a right bar has less value than the current bar.

If we are storing the index in ascending order of values in stack, we know the left border for a stack element would be the adjacent left element. And while adding, when we encounter a new index where value is smaller than stack top element, we would have found the right border of the stack top.

The time complexity would be O(n) as bars can be added & removed only once from the stack. Below you can find the Java program that solves the problem.




 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
import java.util.*;
import java.lang.*;
import java.io.*;

class Solution {
    public int largestRectangleArea(ArrayList<Integer> A) {
        int maxArea = 0;
        //stack keeping index of elements in ascending order
        Stack<Integer> stack = new Stack<Integer>();
        int i = 0;
        for(; i < A.size();){
            if(stack.isEmpty() || A.get(stack.peek()) <= A.get(i)){
                stack.push(i);
                i++;
            } else {
                int currentIndex = stack.pop();
                //left border of a element is the previous index with lower value
                int leftBorder = stack.isEmpty() ? -1 : stack.peek();
                int area = A.get(currentIndex) * (i - leftBorder - 1);
                if(maxArea < area){
                    maxArea = area;
                }
            }
        }
        while(!stack.isEmpty()){
            int currentIndex = stack.pop();
            int leftBorder = stack.isEmpty() ? -1 : stack.peek();
            int area = A.get(currentIndex) * (i - leftBorder - 1);
            if(maxArea < area){
                maxArea = area;
            }
        }
        return maxArea;
    }
}

Comments