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.

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; } } |

## No comments:

## Post a comment