It is widely agreed that technical interviews for product-based companies, such as Microsoft and Amazon, can be difficult to pass. You require lots of practice with competitive problems and technical knowledge to get into your dream company. To help you with the same, here we present one such competitive problem that is “Largest Rectangle in Histogram” mostly asked during interviews for Facebook, Amazon, and Google. Here we understand the problem statement and basic approaches to solving this problem using their algorithms and implementation. So, let's begin!
Given an array of integer 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.
Note that a histogram is a graphical display of numerical data using rectangles of different heights. The rectangles are arranged in the same order as the corresponding elements in the array.
Heights = [2, 1, 5, 6, 2, 3]
Below are three approaches by which you can find the largest rectangle in the histogram. Let us understand in detail below:
Method 1: Using the brute force approach
The key idea to take away is that the height of the maximum area between any two bars will always be bounded by the height of the shortest bar lying between them. Below is an image demonstrating this concept.
The algorithm's time complexity is O(N^3), where N is the size of the array. Similarly, the space complexity of the above problem is O(1) as no extra space is required while using this approach.
Method 2: Using the divide & conquer approach
The divide-and-conquer algorithm is designed to avoid traversing through every element in two arrays. Therefore, instead of traversing through every element from A[i] and A[j], you can apply the divide and conquer algorithm as shown in the below image.
If you clearly observe the above image, you’ll identify the below two outcomes:
- The rectangle with the greatest area has a width and a height equal to the shortest bar.
- The area of the rectangle formed on the right and left side of the minimum height
As you have divided your problem, you need to conquer the solution simply depending on the recursion.
The time complexity for the divide and conquer approach for finding the largest rectangle in the histogram is O(NlogN), where N is the size of the array. similarly, the space complexity of the approach is O(N) as the approach uses the extra array to find the area.
Method 3: Using the stack data structure
The concept is similar to stack-based searching for the Next Greater element. Instead of looking for the next larger element, we will use two arrays left and right to represent the smaller elements on the left and right respectively. For a better understanding, have a look at the below image:
C++ Code for Finding Largest Rectangle in Histogram
Java Code for Finding Largest Rectangle in Histogram
Python Code for Finding Largest Rectangle in Histogram
The time complexity to find the largest rectangle in the histogram using stack is O(N) where N is the size of the array. Similarly, the space complexity is O(N) as we make use of stack data structure to store the elements.
Comparison of Different Solutions
Using Brute Force Approach
Using Divide and Conquer Approach
Practicing competitive problems in advance gives you a cutting edge while interviewing with any company. It helps you feel comfortable and present yourself with the best possible knowledge you carry. To help with the same, we discuss one such competitive problem to find the largest rectangle in histogram along with three different approaches and its algorithm.
It is recommended to get yourself prepared with all the necessary practice you require to get into your dream company and if you get stuck anywhere, our live coding help tutors are always ready to help you.