Largest Rectangle in a Histogram-Interview Problem

Largest Rectangle in Histogram-Interview Problem

Difficulty: Hard

Asked in: Facebook, Amazon, Google

Understanding the Problem:

You are given an array of integers arr where each element represents the height of a bar in a histogram. A Histogram is a graphical display of data using bars of different heights. The bars are placed in the exact same sequence as given in the array. You need to find the area of the largest rectangle found in the given histogram.

For example:

Possible questions to ask the interviewer: →

What is the width of each bar? ( Ans: 1 Unit )
Can I alter the sequence of the bars? ( Ans: No, you can not change it. )

You can give this question a try here . Come back and you can see the below solutions for reference.

Solutions

For the given problem, we are going to discuss three solutions. Starting from the very simple brute force solution and then optimizing it using divide and conquer and finally coming up with the most efficient solution using a stack data structure.

Solution I — Brute Force
Solution II — Using Divide & Conquer
Solution III — Using Stack

Solution I- Brute Force

Solution idea

In this brute force solution, we will simply start traversing the bars in the histogram. For each bar, we will move from right to left(from that bar) and will traverse each bar till the starting bar. For example, if we are at bar 2 we will traverse from bar 2 to bar 0. While traversing, we will find the maximum area possible for a rectangle. For finding the maximum area, we will maintain a minimum height for which a rectangle is possible and we know the width of each bar is 1 unit. By maintaining the minHeight applicable for each bar to be part of a rectangle, we can easily compute the area of the rectangle. After computing the area, we can compare the new area with the previously stored maxArea(variable for storing max area till now). If the value of this new area is greater, then we will update the maxArea. We will keep doing this for each bar in the histogram.

Solution steps

Initially, we will declare two variables maxArea and minHeight and will initialize them both to 0(height and area cannot be negative).
Now, we will iterate the given array arr which has heights for each bar in the histogram.
We will update maxArea, if the area of a single bar given by height arr[i] is greater than the value stored in maxArea.
We will update the minHeight for rectangle with arr[i] for now.
We will traverse all the bars which are on the left of the current bar. And for each bar in this traversal we will find the area of the rectangle possible by finding the minHeight(by comparing heights) and width(by simple calculation).
If the area is greater than the area stored in maxArea, we will update maxArea.
After the entire iteration is done, we will output the maxArea which will give us the area of the largest rectangle possible in the given histogram.

Pseudo-code

int getLargestRect(int arr[])
{
    int maxArea = 0
    int minHeight = 0
    for(int i = 0 to arr.length; i+=1)
    { 
       maxArea = Math.max(arr[i], maxArea)
       minHeight = arr[i]
       for(int j = i-1 to 0 ; j-=1)
       {
          minHeight = Math.min(arr[j], minHeight)
          int width = (j-i+1)
          maxArea = Math.max(maxArea, (minHeight*width))
       }
    }
       return maxArea
}

Complexity Analysis

Time Complexity: O(N²)

Space Complexity: O(1)

Critical ideas to think!

Do you think we need to traverse all the way starting from a bar to the first bar in order to get the largest rectangle? Is there any better way rather traversing all the way from right to left?

Solution II-Using Divide & Conquer

Solution idea

The idea for this approach is instead of a simple one-by-one traversal of each bar and find the area starting from that bar, we will use the divide and conquer algorithm. You can read more about this algorithm here . Using this algorithm and dividing our histogram on the basis of minimum height(of the bars), we can solve this problem much efficiently. Once we have the minimum height, what will be the maximum rectangular area if we divide the histogram on the basis of this bar? The largest area possible for the rectangle will be the maximum of these values:

Area of the largest rectangle formed on the left side of the minimum height.
Area of the largest rectangle formed on the right side of the minimum height.
Area of the rectangle formed by taking minimum height as height and number of bars as the width of the rectangle.

As we have divided our problem, we are ready to conquer the solution simply depending on recursion(which will find us the maximum value out of these three). Do you see any problem here? What will be the worst complexity when then the minimum height is the last bar’s height? O(N²) right? What is the benefit of this solution then? Well, we can optimize this complexity if we can find the minimum height in less than O(N) complexity. Do you see any approach to this? We will use a segment tree for finding the minimum height bar in O(logN). Segment tree is used to perform range-based queries in LogN complexity after it is built. You can read more about it and how it is used for range based problems. Here, we will first build the segment tree which is a one-time operation and then will use it to find the min-height bar.

Solution steps

We will broadly categorize the problem into three steps: →

Building the segment tree with the given histogram array.
We will find the minimum height(of the bar) using this segment tree.
We will divide the finding the area into three sub-problems as discussed and will recursively call for each and then return the maximum out of those.

Pseudo-code

void buildSegmentTree(int tree[], int arr[], int low, int high, int index)
{
    if(low == high)
    {
       tree[index] = arr[low]
    }
    int mid = (low + high)/2
    buildSegmentTree(tree, arr, low, mid, 2*index)
    buildSegmentTree(tree, arr, mid+1, high, 2*index+1)
    tree[index] = min(tree[2*index], tree[2*index+1]
}
int findMinHeightIndex(int tree[], int left, int right, int low, int high, int index)
{
    if(low == left and high == right)
    {
       return index
    }
    int mid = (low+high)/2
   if(right < mid)
       return findMinHeightIndex(tree, left, right, low, mid, 2*index)
   if(left > mid)
       return findMinHeightIndex(tree, left, right, mid+1, high, 2*index+1)
   return min(findMinHeightIndex(tree, left, mid, low, mid, 2*index), findMinHeightIndex(tree, mid+1, right, mid+1, high, 2*index+1)
}
int getLargestRecUtil(int arr[], int tree[], int start, int end, int totalSize)
{
    if(start > end)
       return -1
   if(start == end)
       return arr[start]
   minIndex = findMinHeightIndex(tree, start, end, 0, size-1, 0)
   return max(getLargestRecUtil(arr, tree, start, minIndex-1, totalSize), getLargestRecUtil(arr, tree, minIndex+1, end, totalSize), ((end-start)+1)*arr[minIndex])
}
int getLargestRec(int arr[], int size)
{
   int tree[]
   buildSegmentTree(tree, arr, 0, size-1, 0)
   return getLargestRecUtil(arr, tree, 0, size-1, size)
}

Complexity Analysis

Time Complexity: O(NlogN)

Space Complexity: O(2N)

Critical ideas to think!

Can you think about the space complexity, why it is 2N? ( Hint: The segment tree is a complete binary tree.)
Can we optimise above solution more in terms of space complexity using a Fenwick tree?

Solution III-Using Stack

Solution idea

The thought process behind this approach is to find the area of the rectangle possible considering each bar as the bar with minimum height. Now, how will we do this? How to make each bar of minimum height. We can do this if we know which the first bar on the left side of that bar is having less height and similarly which the first bar on the right side is having less height. By finding those first lefts and right bars with smaller height than the current bar, we can make a rectangle where the height will be the height of that current bar. We can compare the area of this rectangle with the global max area and if the value of this area is greater than the global max, we can update our global max. Now, one more thing how can we find the first bar on the left and right side of the current bar with a smaller height(w.r.t. current bar). To solve this problem, we will use stack and we will call these two smaller bar (on left and right) as leftSmaller and rightSmaller.We will add the first bar’s index to the stack and will start iterating the array arr. If we encounter index whose corresponding heights are greater than the current top of the stack, we will keep adding the them to the stack. At any time, if we get an index for which the height is smaller than the height at the current top, we will start popping the indices out until we get an index whose height is greater or equal to the current index(to be pushed in). For each popped index we will calculate the area and compare this area with the global max.

Solution steps

Create a stack S and add the first index of the arr into S.
Iterate through the array arr and compare the height at the corresponding indices.
If the height is greater or equal to the arr[S.peek()], we can add those indices to the stack.
Else if the height is smaller, we will pop the indices until this condition is met arr[S.peek()] ≤ arr[currentIndex] or the stack becomes empty.
For each popping of the index, we will calculate the area of the largest rectangle possible with the corresponding height taken into account.
We will compare the area with the global max and will update global max if this area is greater.
We will use the formula of width as i (current position where we will push the new data) if the stack is empty and [i-S.peek()-1] is the stack is not empty.

Pseudo-code

int getLargestRect(int arr[], int size)
{
    if(size == 0)
       return 0
    if(size == 1)
       return arr[0]
    Stack <Integer> S
    int maxArea = 0
    S.add(0) //adding the first index
    for(int i= 1 to size-1; i+=1)
    {
       if(arr[i] >= S.peek())
          S.add(i)
       else
       {
           while(!S.isEmpty() && arr[S.peek()] > arr[i])
           {
              int curr = arr[S.pop()]
              if(S.isEmpty())
                 maxArea = max(maxArea, curr*i)
              else
              {
                 maxArea = max(maxArea, curr*(i-S.peek()-1))
              }
           }
           S.add(i)
       }
    }
 
    if(!S.isEmpty())
    {
       int i = size 
       while(!S.isEmpty())
       {
          int curr = arr[S.pop()]
          if(S.isEmpty())
             maxArea = max(maxArea, curr*i)
         else
             maxArea = max(maxArea, curr*(i-S.peek()-1))
      }
    }
    return maxArea
}

Complexity Analysis

Time Complexity: O(N)

Space Complexity: O(N)

Critical ideas to think!