Largest Rectangle in Histogram

Largest Rectangle in Histogram - LeetCode

https://www.geeksforgeeks.org/largest-rectangle-under-histogram/

Given an array of integers heights representing the histogram's bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram.

Input: heights = [6, 2, 5, 4, 5, 1, 6]
Output: 12
Explanation: The above is a histogram where width of each bar is 1.
The largest rectangle is shown in the red area, which has an area = 12 units.

This is the most important question, as we can check on Leetcode it is identified as Hard Problem.

Let’s discuss the approach to solve this problem.

As we can this is the variation of NearestSmallestToLeft and NearestSmallestToRight Problem.

Note : (Took -1 if the index or element not exist)

NearestSmallestToLeft: https://www.geeksforgeeks.org/find-the-nearest-smaller-numbers-on-left-side-in-an-array/

Let’s say we have an array int arr[] = {6, 2, 5, 4, 5, 1, 6 }, Then all the NearestSmallestToLeft are : {-1 , -1 , 2 , 2 , 4 , -1 , 1 } , or if we store index then the array become {-1 , -1 , 1 , 1, 3 , -1 , 5}.

NearestSmallerToRight: https://www.geeksforgeeks.org/next-smaller-element/

Let’s say we have an array int arr[] = {6, 2, 5, 4, 5, 1, 6 }, Then all the NearestSmallestToLeft are : {2 , 1, 4, 1, 1, -1, -1} , or if we store index then the array become {1, 5, 3, 5, 5, -1, -1}.

Now we have :

NearestSmallestToLeft : {-1 , -1 , 1 , 1, 3 , -1 , 5} & NearestSmallerToRight : {1, 5, 3, 5, 5, 7, 7}(Here instead of -1 as index took index 1 more than last index if the smallest element not found over right side).

Now: We need to find the width of the Rectangle.

Width = Right-Left -1; This will give us an array : {1 , 5 , 1 , 3 , 1 , 7 , 1 }

Now only we need to Multiply the width array with the height we already have(heights = {6, 2, 5, 4, 5, 1, 6}) and find out the maximum area. This will become our solution.

Area [] = Height * Width;

Here Area [] = {6,10, 5, 12, 5, 7, 6 }12 is the maximum and is the answer also.

Let’s Jump to the Coding part:

class MAH{
 int val;
 int index;
 
 public MAH(int val,int index) {
  this.val = val;
  this.index = index;
 }
}
class Solution {
    public int largestRectangleArea(int[] heights) {
        List<Integer> left = findMinimumToLeft(heights);
     List<Integer> right = findMinimumToRight(heights);
        
        int maxArea = 0;
 for(int i=0;i<left.size();i++) {
  int width = (right.get(i) - left.get(i) -1);
  int height = heights[i];
  
  if((height * width)>maxArea)
   maxArea = height * width;
 }
 return maxArea;
    }
    public static List<Integer> findMinimumToLeft(int[]arr) {
  Stack<MAH> stack = new Stack<MAH>();
  List<Integer> list = new ArrayList<Integer>();
  for(int i =0;i<arr.length;i++) {
   if(stack.isEmpty())
    list.add(-1);
   else if(!stack.isEmpty() && stack.peek().val<arr[i]) {
    list.add(stack.peek().index);
   }
   else if(!stack.isEmpty() && stack.peek().val>=arr[i]) {
    while(!stack.isEmpty() && stack.peek().val>=arr[i]) {
     stack.pop();
    }
    if(stack.isEmpty()) {
     list.add(-1);
    }
    else {
     list.add(stack.peek().index);
    }
   }
   stack.add(new MAH(arr[i], i)); 
  }
  return list;
 }
public static List<Integer> findMinimumToRight(int[]arr) {
  Stack<MAH> stack = new Stack<MAH>();
  List<Integer> list = new ArrayList<Integer>();
  for(int i =arr.length-1;i>=0;i--) {
   if(stack.isEmpty())
    list.add(arr.length);
   else if(!stack.isEmpty() && stack.peek().val<arr[i]) {
    list.add(stack.peek().index);
   }
   else if(!stack.isEmpty() && stack.peek().val>=arr[i]) {
    while(!stack.isEmpty() && stack.peek().val>=arr[i]) {
     stack.pop();
    }
    if(stack.isEmpty()) {
     list.add(arr.length);
    }
    else {
     list.add(stack.peek().index);
    }
   }
   stack.add(new MAH(arr[i],i)); 
  }
  Collections.reverse(list);
  return list;
 }
}

Thankyou for reading!!

Happy Coding.