Largest Rectangle in Histogram

HARD

Description

Given an array of integers 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.

Example 1:

Input: heights = [2,1,5,6,2,3]
Output: 10
Explanation: The above is a histogram where width of each bar is 1.
The largest rectangle is shown in the red area, which has an area = 10 units.

Example 2:

Input: heights = [2,4]
Output: 4

Constraints:

1 <= heights.length <= 10⁵
0 <= heights[i] <= 10⁴

Approaches

Checkout 3 different approaches to solve Largest Rectangle in Histogram. Click on different approaches to view the approach and algorithm in detail.

Brute Force Approach

The most straightforward approach is to consider every possible rectangle. We can iterate through all possible pairs of bars and treat them as the left and right boundaries of a rectangle. For each pair, we find the minimum height within that range and calculate the area. The maximum area found among all pairs is the result.

Algorithm

Initialize maxArea = 0.
Iterate through each bar i from 0 to n-1.
For each bar i, treat it as the minimum height of a potential rectangle.
Expand to the left from i to find the first bar shorter than heights[i]. This determines the left boundary.
Expand to the right from i to find the first bar shorter than heights[i]. This determines the right boundary.
Calculate the width using the left and right boundaries.
Calculate the area: heights[i] * width.
Update maxArea with the maximum area found so far.
Return maxArea.

This method iterates through each bar of the histogram and considers it as the bar of minimum height for a potential largest rectangle. For each bar i with height h = heights[i], we need to find the maximum possible width. This width is determined by extending to the left and right from bar i as long as the bars encountered are taller than or equal to h.

The algorithm proceeds as follows:

Initialize a variable maxArea to 0.
Iterate through the heights array with an index i from 0 to n-1, where n is the number of bars.
For each bar i, we expand outwards to find the boundaries of the largest rectangle that has heights[i] as its height.
- Find the left boundary: Start a pointer l from i and move left (l--) as long as l >= 0 and heights[l] >= heights[i].
- Find the right boundary: Start a pointer r from i and move right (r++) as long as r < n and heights[r] >= heights[i].
The width of this rectangle is r - l - 1.
Calculate the area: area = heights[i] * (r - l - 1).
Update maxArea = max(maxArea, area).
After iterating through all bars, maxArea will hold the area of the largest rectangle.

public class Solution {
    public int largestRectangleArea(int[] heights) {
        int maxArea = 0;
        int n = heights.length;
        for (int i = 0; i < n; i++) {
            int left = i;
            while (left - 1 >= 0 && heights[left - 1] >= heights[i]) {
                left--;
            }
            int right = i;
            while (right + 1 < n && heights[right + 1] >= heights[i]) {
                right++;
            }
            int width = right - left + 1;
            maxArea = Math.max(maxArea, heights[i] * width);
        }
        return maxArea;
    }
}

Complexity Analysis

Time Complexity: O(n^2)Space Complexity: O(1)

Pros and Cons

Pros:

Simple to understand and implement.
Requires no extra space.

Cons:

Inefficient for large inputs due to its quadratic time complexity.
Leads to 'Time Limit Exceeded' on most online judges.

Code Solutions

Checking out 4 solutions in different languages for Largest Rectangle in Histogram. Click on different languages to view the code.

using System ; using System.Collections.Generic ; using System.Linq ; public class Solution { public int LargestRectangleArea ( int [] height ) { var stack = new Stack < int >(); var result = 0 ; var i = 0 ; while ( i < height . Length || stack . Any ()) { if (! stack . Any () || ( i < height . Length && height [ stack . Peek ()] < height [ i ])) { stack . Push ( i ); ++ i ; } else { var previousIndex = stack . Pop (); var area = height [ previousIndex ] * ( stack . Any () ? ( i - stack . Peek () - 1 ) : i ); result = Math . Max ( result , area ); } } return result ; } }

Video Solution

Watch the video walkthrough for Largest Rectangle in Histogram

Data Structures:

ArrayStackMonotonic Stack

Companies:

Adobe |Amazon |Apple |Bloomberg |