84. Largest Rectangle in Histogram

HardStackArrayMonotonic Stack
Leetcode Link

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 and right arrays to keep track of the bounds for the largest rectangle with height[i] as the smallest bar. left[i] will store the index of the first bar to the left that is shorter than height[i], and right[i] will store the index of the first bar to the right that is shorter than height[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 index i:

    • 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 the right 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 the left[i] to that index.
    • We then push i onto the stack, since it might be the potential left bound for a future bar.

  • 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 height heights[i] of the bar to get the area of the largest rectangle with the bar at i 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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

A heap is a ...?

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:

  1. Initializing Data Structures: A stack stk is initialized as an empty list, which will store indices of bars. Two lists left and right are also initialized to store the left and right bounds for each bar (-1 for left and n for right, respectively, where n is the number of bars).

  2. Traversing Heights: We loop through each bar using its index i and height h:

    • 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 bar h.

    • 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, the left boundary for the current bar h 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.

  3. Calculating the Largest Area: Once the traversal is done, we have left and right arrays filled with the bounds of potential rectangles for each bar. To calculate the largest area:

    • Iterate over each index i and corresponding height h, and calculate the width for the largest rectangle that can be formed with height h by subtracting left[i] from right[i] and subtracting 1 (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.

  4. 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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which data structure is used to implement priority queue?

Example 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].

  1. Initializing Data Structures:

    1stk = []
2left = [-1] * len(heights)
3right = [len(heights)] * len(heights)

  2. 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 height 1 is less than the height at the top of the stack 2. We pop from the stack (popping 0):

      stk = []

      We update right[0] = 1 and since stk is now empty, we push the current index 1 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 since 2 is less than 6 and 5. After popping 3 and 2:

      stk = [1]

      We update right[3] = 4, right[2] = 4. The stack still has 1 in it, so left[4] = 1. Push 4 onto the stack:

      stk = [1, 4]

    • For heights[5] (3):

      stk = [1, 4, 5]

  3. Calculating the Largest Area:

    • We've completed the traversal, left = [-1, -1, 1, 2, 1, 4] and right = [6, 2, 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 (for heights[2]).

  4. Return the Largest Area:

    • The maximum calculated area is 10, which is the area of the largest rectangle in the histogram we started with.

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
Not Sure What to Study? Take the 2-min Quiz：

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8
1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12
1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

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, and stk, and also iterates over the input heights list twice (once for populating the left and right lists, and once for calculating the maximum area). Each element of the heights list is processed exactly once during these iterations, leading to O(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 in heights, 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 the right 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 of O(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, and right lists, each of size n, where n is the number of elements in the input heights list. Thus, the space complexity is O(n), correlating with the size of the input.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which of the following array represent a max heap?

Recommended Readings

Stack Intro

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/Queue Intro

Monotonic Stack Deque Intro If you'd prefer a video iframe width 560 height 315 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 The word monotonic means a list or a

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫