84. Largest Rectangle in Histogram
Problem Description
The task is to find the largest rectangular area in a histogram, which consists of a series of adjacent bars of varying heights. Each bar has a uniform width of 1
unit, and the height of each bar corresponds to each integer in the given heights
array. To elaborate, imagine drawing rectangles starting from the base of each bar and extending them as wide as possible without crossing the height of shorter bars adjacent to it. The goal is to determine the maximum area covered by such a rectangle.
Intuition
The intuition behind the solution involves using a stack and a concept called "Monotonic Stack" which helps us process the bars in a way that we can calculate the maximum width for each bar where it remains the tallest bar within that width.
Here is the reasoning for each step in the algorithm:
-
We initialize
left
andright
arrays to keep track of the bounds for the largest rectangle withheight[i]
as the smallest bar.left[i]
will store the index of the first bar to the left that is shorter thanheight[i]
, andright[i]
will store the index of the first bar to the right that is shorter thanheight[i]
. -
We traverse the heights while using a stack
stk
to maintain indices of bars in a non-decreasing order. The stack will help us in finding the left and right bounds for each bar. -
For each bar
h
with indexi
:- We pop from the stack while the bar at the top of the stack has a height greater than or equal to
h
. Each time we pop, we update theright
bound for the popped index because we just found a shorter bar on the right. - If the stack is not empty after popping, it means the bar on the top of the stack is the first bar to the left of
h
that is shorter, so we update theleft[i]
to that index. - We then push
i
onto the stack, since it might be the potential left bound for a future bar.
- We pop from the stack while the bar at the top of the stack has a height greater than or equal to
-
After we have the left and right bounds for each bar, the maximum possible width for each bar is given as
(right[i] - left[i] - 1)
. We multiply this with the heightheights[i]
of the bar to get the area of the largest rectangle with the bar ati
being the shortest bar. We calculate this for every bar. -
Finally, we return the maximum area out of all the areas we have computed.
This algorithm is efficient because each bar is pushed and popped from the stack exactly once, and the left and right bounds are updated during this process. We're leveraging the stack to perform all necessary computations as we iterate through the histogram, which allows us to compute the largest rectangle in linear time.
Learn more about Stack and Monotonic Stack patterns.
Solution Approach
The solution is implemented in Python using a single-pass algorithm with a stack data structure to maintain a history of bars that are yet to find a shorter bar on the right. The goal is to calculate the correct left
and right
bounds for each bar, which will then allow us to calculate the area of the largest rectangle that can be formed with each bar as the shortest one in that rectangle.
Here's a step-by-step breakdown of the algorithm:
-
Initializing Data Structures: A stack
stk
is initialized as an empty list, which will store indices of bars. Two listsleft
andright
are also initialized to store the left and right bounds for each bar (-1
forleft
andn
forright
, respectively, wheren
is the number of bars). -
Traversing Heights: We loop through each bar using its index
i
and heighth
:-
While the top of the stack is not empty and the current height
h
is less than or equal to the height at the index on top of the stack, we pop from the stack. This indicates that we have found a right boundary for the rectangle concerning the bar at the index that was just popped. -
For each index we pop from the stack, we use it to set the corresponding
right
bound for that bar to the current index (i
), since we now know this bar is taller than the current barh
. -
If there are still elements left in the stack after popping, it indicates that the current bar
h
is larger than the bar at the top of the stack. Hence, theleft
boundary for the current barh
is now known to be the index on top of the stack. -
Finally, we add the current index
i
to the top of the stack.
-
-
Calculating the Largest Area: Once the traversal is done, we have
left
andright
arrays filled with the bounds of potential rectangles for each bar. To calculate the largest area:-
Iterate over each index
i
and corresponding heighth
, and calculate the width for the largest rectangle that can be formed with heighth
by subtractingleft[i]
fromright[i]
and subtracting1
(as the boundaries are exclusive). -
Calculate the area for each rectangle by multiplying its height (
heights[i]
) with the width calculated above. -
Use the
max
function to determine the largest area from these.
-
-
Return the Largest Area: After iteration, return the maximum area calculated, which is the area of the largest rectangle in the histogram.
The code snippet provided uses list comprehension at the end to perform the calculation of the areas and find the maximum all in one line, showcasing an efficient Pythonic approach:
return max(h * (right[i] - left[i] - 1) for i, h in enumerate(heights))
This algorithm uses a stack efficiently that follows the Last-In-First-Out (LIFO) principle, whereby each element is pushed and popped only once, resulting in a time complexity of O(n)
where n
is the number of bars in the histogram.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach with a small example. Consider the heights
array:
1heights = [2, 1, 5, 6, 2, 3]
This represents a histogram with 6 bars where the heights of the bars are [2, 1, 5, 6, 2, 3]
.
-
Initializing Data Structures:
1stk = [] 2left = [-1] * len(heights) 3right = [len(heights)] * len(heights)
-
Traversing Heights: We start traversing the
heights
array.-
For
heights[0]
, since the stack is empty, no action is taken other than pushing the index onto the stack:stk = [0]
-
For
heights[1]
, the current height1
is less than the height at the top of the stack2
. We pop from the stack (popping0
):stk = []
We update
right[0] = 1
and sincestk
is now empty, we push the current index1
onto the stack:stk = [1]
-
For
heights[2]
(5
), the stack action yields:stk = [1, 2]
-
For
heights[3]
(6
):stk = [1, 2, 3]
-
For
heights[4]
(2
), we start popping since2
is less than6
and5
. After popping3
and2
:stk = [1]
We update
right[3] = 4
,right[2] = 4
. The stack still has1
in it, soleft[4] = 1
. Push4
onto the stack:stk = [1, 4]
-
For
heights[5]
(3
):stk = [1, 4, 5]
-
-
Calculating the Largest Area:
-
We've completed the traversal,
left = [-1, -1, 1, 2, 1, 4]
andright = [1, 6, 4, 4, 6, 6]
. -
Calculate the widths and areas for each bar; for example:
-
For
i=2
(height = 5
):width = right[2] - left[2] - 1 = 4 - 1 - 1 = 2
area = heights[2] * width = 5 * 2 = 10
-
Repeat this for each bar and find the max area:
areas = [2 * (1 - (-1) - 1), 1 * (6 - (-1) - 1), ... ]
After evaluating all areas, the largest one is
10
(forheights[2]
).
-
-
-
Return the Largest Area:
- The maximum calculated area is
10
, which is the area of the largest rectangle in the histogram we started with.
- The maximum calculated area is
Solution Implementation
1from typing import List
2
3class Solution:
4 def largestRectangleArea(self, heights: List[int]) -> int:
5 # Get the total number of bars in the histogram
6 num_bars = len(heights)
7
8 # Initialize stacks for indexes of bars
9 stack = []
10
11 # Initialize arrays to record the first smaller bar on the left of each bar
12 smaller_left_index = [-1] * num_bars
13
14 # Initialize arrays to record the first smaller bar on the right of each bar
15 smaller_right_index = [num_bars] * num_bars
16
17 # Iterate over all heights to compute the smaller_left_index and smaller_right_index
18 for index, height in enumerate(heights):
19 # Pop elements from the stack while the current height is less than
20 # the top element's height in the stack to find the right boundary
21 while stack and heights[stack[-1]] >= height:
22 smaller_right_index[stack[-1]] = index
23 stack.pop()
24 # If the stack is not empty, the current element at the top is the previous
25 # bar of smaller height (left boundary)
26 if stack:
27 smaller_left_index[index] = stack[-1]
28 # Push this bar onto stack
29 stack.append(index)
30
31 # Calculate the maximum area of rectangle in histogram
32 max_area = 0
33 for i, h in enumerate(heights):
34 # Update max_area with the larger area found
35 max_area = max(max_area, h * (smaller_right_index[i] - smaller_left_index[i] - 1))
36
37 return max_area
38
1class Solution {
2 public int largestRectangleArea(int[] heights) {
3 int maxArea = 0; // This variable will store the maximum area found.
4 int length = heights.length; // Total number of bars.
5
6 // Stack to keep track of indices of the bars.
7 Deque<Integer> stack = new ArrayDeque<>();
8
9 // Arrays to keep track of the left and right boundaries of each bar.
10 int[] leftBoundary = new int[length];
11 int[] rightBoundary = new int[length];
12
13 // Initialize right boundaries as the length of the array.
14 Arrays.fill(rightBoundary, length);
15
16 // Iterate over all bars to calculate left and right boundaries.
17 for (int i = 0; i < length; ++i) {
18 // Pop elements from the stack until the current bar is taller than the stack's top
19 // and set their right boundary to the current bar's index.
20 while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) {
21 rightBoundary[stack.pop()] = i;
22 }
23
24 // If the stack is empty, then there's no smaller bar to the left.
25 // Otherwise, the stack's top is the previous smaller bar's index.
26 leftBoundary[i] = stack.isEmpty() ? -1 : stack.peek();
27
28 // Push the current index onto the stack.
29 stack.push(i);
30 }
31
32 // Calculate the largest rectangle area for each bar using their boundaries.
33 for (int i = 0; i < length; ++i) {
34 // Calculate width of the current bar's largest rectangle.
35 int width = rightBoundary[i] - leftBoundary[i] - 1;
36 // Calculate area and update maxArea if it's larger.
37 maxArea = Math.max(maxArea, heights[i] * width);
38 }
39
40 // Return the maximum area found.
41 return maxArea;
42 }
43}
44
1#include <vector>
2#include <stack>
3using namespace std;
4
5class Solution {
6public:
7 int largestRectangleArea(vector<int>& heights) {
8 // The maximum area found so far.
9 int maxArea = 0;
10 // The total number of bars.
11 int numBars = heights.size();
12 // Stack to keep track of the indices of the bars.
13 stack<int> indexStack;
14 // Vector to store the index of the left nearest smaller bar for each bar.
15 vector<int> leftNearest(numBars, -1);
16 // Vector to store the index of the right nearest smaller bar for each bar.
17 vector<int> rightNearest(numBars, numBars);
18
19 for (int i = 0; i < numBars; ++i) {
20 // Pop elements from the stack until the current bar is taller than the stack's top bar.
21 while (!indexStack.empty() && heights[indexStack.top()] >= heights[i]) {
22 // Set the right nearest smaller bar for the popped bar.
23 rightNearest[indexStack.top()] = i;
24 indexStack.pop();
25 }
26 // If the stack is not empty, then the current top is the left nearest smaller bar.
27 if (!indexStack.empty()) leftNearest[i] = indexStack.top();
28 // Push current bar to stack.
29 indexStack.push(i);
30 }
31
32 // Calculate the maximum area for each bar considering the nearest smaller bars to the left and right.
33 for (int i = 0; i < numBars; ++i)
34 maxArea = max(maxArea, heights[i] * (rightNearest[i] - leftNearest[i] - 1));
35
36 // Return the maximum area found.
37 return maxArea;
38 }
39};
40
1// TypeScript doesn't have predefined Stack class, so we use an array to simulate stack behavior.
2let indexStack: number[] = [];
3let maxArea: number = 0;
4let heights: number[];
5
6// Variables leftNearest and rightNearest are declared globally to be used in functions below.
7let leftNearest: number[];
8let rightNearest: number[];
9
10// Finds the largest rectangle area in a histogram.
11function largestRectangleArea(inputHeights: number[]): number {
12 heights = inputHeights; // Initialize global heights variable with the input.
13 indexStack = []; // Reset the stack for the new calculation.
14 maxArea = 0; // Reset the maximum area for the new calculation.
15 const numBars = heights.length;
16 leftNearest = new Array(numBars).fill(-1);
17 rightNearest = new Array(numBars).fill(numBars);
18
19 // Fill in values for leftNearest and rightNearest arrays.
20 populateNearestSmallerIndices(numBars);
21
22 // Calculate the maximum area for each bar considering the nearest smaller bars to the left and right.
23 for (let i = 0; i < numBars; ++i) {
24 maxArea = Math.max(maxArea, heights[i] * (rightNearest[i] - leftNearest[i] - 1));
25 }
26
27 return maxArea; // Return the maximum area found.
28}
29
30// Populate the nearest smaller indices on both left and right for each bar
31function populateNearestSmallerIndices(numBars: number) {
32 for (let i = 0; i < numBars; ++i) {
33 // Pop elements from the stack until the current bar is taller than the stack's top bar.
34 while (indexStack.length > 0 && heights[indexStack[indexStack.length - 1]] >= heights[i]) {
35 // Set the right nearest smaller bar for the popped bar.
36 rightNearest[indexStack.pop() as number] = i;
37 }
38 // If the stack is not empty, then the current top is the left nearest smaller bar.
39 if (indexStack.length > 0) leftNearest[i] = indexStack[indexStack.length - 1];
40 // Push current bar to stack.
41 indexStack.push(i);
42 }
43}
44
Time and Space Complexity
The time complexity of the largestRectangleArea
function can be analyzed by looking at the operations performed inside the function.
-
The function initializes three lists named
left
,right
, andstk
, and also iterates over the inputheights
list twice (once for populating theleft
andright
lists, and once for calculating the maximum area). Each element of theheights
list is processed exactly once during these iterations, leading toO(n)
time for each loop. -
The stack
stk
is used to keep track of the indices of the rectangles in ascending order of their heights. For each element inheights
, the stack may perform a push operation (stk.append(i)
). Additionally, while the current height is less than or equal to the height of the rectangle corresponding to the index at the top of the stack, pop operations occur, and theright
bound for the rectangle is updated. Despite this, each element is added to the stack once and removed from the stack at most once over the entire run of the loop, leading to a total ofO(n)
operations.
Based on these points, the overall time complexity of the largestRectangleArea
function is O(n)
.
As for the space complexity:
- The extra space is used for the
stk
,left
, andright
lists, each of sizen
, wheren
is the number of elements in the inputheights
list. Thus, the space complexity isO(n)
, correlating with the size of the input.
Learn more about how to find time and space complexity quickly using problem constraints.
Given a sorted array of integers and an integer called target, find the element that
equals to the target and return its index. Select the correct code that fills the
___
in the given code snippet.
1def binary_search(arr, target):
2 left, right = 0, len(arr) - 1
3 while left ___ right:
4 mid = (left + right) // 2
5 if arr[mid] == target:
6 return mid
7 if arr[mid] < target:
8 ___ = mid + 1
9 else:
10 ___ = mid - 1
11 return -1
12
1public static int binarySearch(int[] arr, int target) {
2 int left = 0;
3 int right = arr.length - 1;
4
5 while (left ___ right) {
6 int mid = left + (right - left) / 2;
7 if (arr[mid] == target) return mid;
8 if (arr[mid] < target) {
9 ___ = mid + 1;
10 } else {
11 ___ = mid - 1;
12 }
13 }
14 return -1;
15}
16
1function binarySearch(arr, target) {
2 let left = 0;
3 let right = arr.length - 1;
4
5 while (left ___ right) {
6 let mid = left + Math.trunc((right - left) / 2);
7 if (arr[mid] == target) return mid;
8 if (arr[mid] < target) {
9 ___ = mid + 1;
10 } else {
11 ___ = mid - 1;
12 }
13 }
14 return -1;
15}
16
Recommended Readings
Stack Intro Imagine you have a pile of books on your desk If you want to add a new book you place it on top If you want to read a book you take it from the top And if you simply want to see which book is on the top you
Monotonic Stack Deque Intro If you'd prefer a video div class responsive iframe iframe src https www youtube com embed Dq_ObZwTY_Q title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe div The word monotonic means a list or
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.