Table of Contents
Introduction
One of the most feared things by human beings is a failure. The extent to which people push themselves to avoid disappointment is quite surprising, but being prepared is one of the easiest ways to steer clear of it. To quote Abraham Lincoln,
“Give me six hours to chop down a tree, and I will spend the first four sharpening the axe.”
Unlike Mr Lincoln, we are not chopping a tree. Instead, we are planting the seeds to a successful career, and to do that, we must be prepared for the placement exams.
In companies like Facebook and Google, a common question in the coding interview is to find the largest rectangular area in Histogram.
Do you know how to find it?
I guess not. So let’s learn how to find the largest rectangular area in Histogram in this article.
Problem Statement
Before we head on to the solution, we must first correctly understand the largest rectangular area in Histogram.
An array or list “Heights” of length N will be given. The elements of this array are the heights of each bar in a Histogram, and the width of each bar is 1.
For example, if Heights = {3, 2, 6, 5, 1, 2} the Histogram would be as shown below.
For this example, the largest rectangular area in Histogram will be as follows:
Now that we know what question we are solving, we will look into the different methods.
Brute Force Approach
By brute force, we usually mean the most straightforward method which comes to our mind first. Most of the time, this isn’t the best with respect to time complexity.
This method will find the area of all the rectangles possible, starting from each rectangle for our problem.
To understand this better, let us consider our previous example again.
The iterations through all the rectangles to find the largest one is shown below.
To summarise what we learnt, let’s see the algorithm and code for the brute force algorithm.
Algorithm
Step 1: Initialise a variable, maxArea, with 0. Step 2: Create a for loop which runs through all the rectangles. Step 3: Create a nested loop to find all the possible rectangles, starting from a particular one. Step 4: Store current index value as both min and max values in minVal and max Val variable, respectively. Step 4: Find the area of the rectangles formed compare with maxArea and assign maxArea as maxVal if it’s greater. Step 5: Return maxArea as the largest rectangular area in Histogram.
Python Code
'''
Time Complexity = O(N^2)
Space Complexity = O(1)
Where N is the number of elements in the given array/list.
'''
def largestRectangle(heights):
n = len(heights)
if n <= 0:
return 0;
maxArea = 0;
for j in range(n):
# Store current index value as both min and max values.
minVal = heights[j]
maxVal = heights[j]
i = j - 1
while i >= 0:
# If the current index value is less than minVal.
if heights[i] < minVal:
minVal = heights[i]
# If the area of the current rectangle is greater than maxVal.
if minVal * (j - i + 1) > maxVal:
maxVal = minVal * (j - i + 1);
# Store the maximum area of the rectangle.
if maxVal > maxArea:
maxArea = maxVal;
i -= 1
# Return area of largest rectangle.
return maxArea
heights = [3,2,6,5,1,2]
print("Maximum area is",largestRectangle(heights))
Output:
Largest rectangular area in histogram is 10
Complexity Analysis
This method has a time complexity of O(N2) due to the nested loop, where N is the number of elements in the given array/list.
Because of that reason, it isn’t usually used.
Space Complexity = O(1).
Divide and Conquer
Our age-old favourite technique of divide and conquer can be used to find the largest rectangular area in Histogram too. Let’s see how it is done with the help of our previous example.
In this method, we first have to find the smallest element in the array. Then we will divide the array into two halves, the part to the left of the smallest element and the part to the right of it.
After this, we will calculate the area of two rectangles:
- The rectangle formed by the elements in the left half
- The rectangle formed by the elements in the right half
The largest area will be saved. Out of the two halves, the one with the largest area is considered, and the process is repeated till we are left with only one element.
Algorithm
The idea is to find the minimum value in the given array/list, which is the lowest histogram bar. Once we have an index of the minimum value, the max area is the maximum of the following three values. The maximum area on the left side of the minimum value. Here we are trying to find the area of the rectangle towards the left side of the minimum value bar, excluding the min value. The maximum area on the right side of the minimum value. Here we are trying to find the area of the rectangle towards the right side of the minimum value bar, excluding the min value. The number of bars is multiplied by the minimum value. We use a loop with two pointers named “LPTR” and “RPTR”, and at each iteration, we advance the one with a higher neighbour until we reach the end in both directions.
Python Code
'''
Time Complexity = O(N log N)
Space Complexity = O(log N)
Where N is the number of elements in the given array/list.
'''
def divideAndConquer(heights, l, r):
# If we only have one element then return it.
if l == r:
return heights[l]
mid = (l + r) // 2
# Recur for the left rectangle.
lscore = divideAndConquer(heights, l, mid)
# Recur for the right rectangle.
rscore = divideAndConquer(heights, mid + 1, r)
lptr = mid
rptr = mid
maxArea = 0
minimum = heights[mid]
while lptr >= l and rptr <= r:
'''
Take the minimum of lptr height and
rptr height in comparison to the minimum.
'''
minimum = min(minimum,heights[lptr], heights[rptr])
'''
Take the maximum area for
the rectangle between lptr and rptr.
'''
maxArea = max(maxArea, minimum * (rptr - lptr + 1))
if (lptr > l) and (rptr < r):
if heights[rptr + 1] >= heights[lptr - 1]:
rptr += 1
else:
lptr -= 1
elif lptr > l:
lptr -= 1
elif rptr < r:
rptr += 1
else:
rptr += 1
lptr -= 1
# Return the maximum area.
return max(maxArea,lscore, rscore)
def largestRectangle(heights):
if len(heights) == 0:
return 0
return divideAndConquer(heights, 0, len(heights) - 1)
heights = [3,2,6,5,1,2]
print("Maximum area is",largestRectangle(heights))
Output:
Largest rectangular area in histogram is 10
Complexity Analysis
Dividing the array into two halves gives us O(log N) complexity, but we repeat that recursively (N-1) times. Therefore, the overall time complexity of the algorithm is O(NlogN), which is better than the complexity of the brute force method,
Space Complexity = O(N), where N is the number of elements in the given array/list.
Using Next Lower Element
While solving any problem, we aim to solve it using an algorithm with linear time complexity. Let us see how to find the largest rectangular area in Histogram in such a manner.
In this method, we will find the next smaller element to the left and right of it for each element. For example, if we consider element 5, the indices of the next smaller element to the left and right are 1 and 4. respectively.
With these indices, we can find the width of the largest possible rectangle for that element as follows:
Area of the rectangle = Element x (Next smaller element to the right – Next smaller element to the left – 1)
= 5 x (4 – 1 – 1) = 5 x 2 = 10
We can find this area for all the rectangles and compare them to find the largest rectangular area in Histogram.
Algorithm
We traverse all histograms from left to the right, maintaining a stack of histograms. Every histogram is pushed to stack once. A histogram is popped from the stack when a histogram of smaller height is seen. When a histogram is popped, we calculate the area with the popped histogram as the smallest histogram. How do we get the left and right indexes of the popped histogram – the current index tells us the ‘RIGHT_INDEX’, and the index of the previous item in the stack is the ‘LEFT_INDEX'. Create an empty stack. Start from the first histogram bar, and do the following for every bar ‘heights[i]’ where ‘I’ varies from 0 to ‘N’-1. If the stack is empty or heights[i] are higher than the bar at the top, push ‘I’ to the stack. If this bar is smaller than the top of the stack, keep removing the top of the stack while the top is greater. Let the removed bar be heights[tp]. Calculate the area of the rectangle with heights[tp] as the smallest bar. For heights[tp], the ‘left index’ is the previous (previous to tp) item in the stack, and the ‘RIGHT_INDEX' is ‘I’ (current index). If the stack is not empty, then one by one, remove all bars from the stack and do step 4 for every removed bar.
Python Code
'''
Time Complexity = O(N)
Space Complexity = O(N)
Where N is the number of elements in the given array/list.
'''
def largestRectangle(heights):
n = len(heights)
'''
The stack holds indexes of heights[] array.
The bars stored in stack are always in increasing
order of their heights.
'''
stack = list()
# Initialize max area.
maxArea = 0
# To store the top of the stack.
topOfStack = 0
# To store an area with the top bar as the smallest bar.
areaWithTop = 0
# Run through all bars of a given histogram.
i = 0
while i < n:
'''
If this bar is higher than the bar on top stack,
push it to stack.
'''
if len(stack) == 0 or (heights[stack[-1]] <= heights[i]):
stack.append(i)
i += 1
else:
topOfStack = stack.pop()
'''
Calculate the area with heights[topOfStack]
stack as the smallest bar.
'''
if len(stack) == 0:
areaWithTop = heights[topOfStack] * i
else:
areaWithTop = heights[topOfStack] * (i - stack[-1] - 1)
# Update max area, if needed.
if maxArea < areaWithTop:
maxArea = areaWithTop
'''
Now pop the remaining bars from stack and
calculate area with every popped
bar as the smallest bar.
'''
while len(stack) != 0:
topOfStack = stack.pop()
if len(stack) == 0:
areaWithTop = heights[topOfStack] * i
else:
areaWithTop = heights[topOfStack] * (i - stack[-1] - 1)
if maxArea < areaWithTop:
maxArea = areaWithTop
return maxArea
heights = [3,2,6,5,1,2]
print("Maximum area is",largestRectangle(heights))
Output:
Largest rectangular area in histogram is 10
Complexity Analysis
As discussed in the beginning, this method has:
Time Complexity = O(N)
Space Complexity = O(N)
Where N is the number of elements in the given array/list.
Frequently Asked Questions
The simplest approach is to consider all bars as starting points and calculate the area of the rectangles possible with each bar.
You can also use the concept of the nearest smallest element to left and right to calculate the largest rectangular area in Histogram.
Stack is an abstract data type that works on the principle of LIFO (last in, first out).
The most optimised solution comes up with the time complexity of O(n).
You can get yourself familiar with the NGE problem here.
Key Takeaways
In this article, we learnt how to find the largest rectangular area in Histogram. You may, however, try solving it yourself here and get your solution checked too. This will provide you with complete knowledge on a question frequently asked in many interviews.
Apart from this, you can practice other questions commonly asked in the coding rounds of interviews at CodeStudio. You will find practice programming questions there, and the interview experiences of people who were once students like us but are now working in renowned product-based companies.
Happy learning!
By: Neelakshi Lahiri
