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 5: Find the area of the rectangles formed compare with maxArea and assign maxArea as maxVal if it’s greater.
Step 6: 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(N^{2}) 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 ageold 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 (N1) 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.
Also read, python filename extensions
Also see, Python data analytics
Frequently Asked Questions
How do you find the largest area of the rectangle in the Histogram?
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.
What are stacks in data structures?
Stack is an abstract data type that works on the principle of LIFO (last in, first out).
What is the best time complexity to find the largest rectangular area in Histogram?
The most optimised solution comes up with the time complexity of O(n).
Conclusion
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.
Recommended Problem  K Closest Points To Origin
Apart from this, you can practice other questions commonly asked in the coding rounds of interviews at Coding Ninjas Studio. 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 productbased companies.
Happy learning!