Coding

Largest rectangle in a histogram

Asked at

Goldman Sachs

Porter

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

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.

Input: heights = [2, 1, 5, 6, 2, 3]

Output: 10

Explanation: The largest rectangle is highlighted, which has an area of 5*2 = 10 units.

Input: heights = [3, 5, 1, 7, 5, 9]

Output: 15

Explanation: The largest rectangle has an area of 5*3 = 15 units.

Input: heights = [2,4]

1 <= heights.length <= 105
0 <= heights[i] <= 104

cpp

class Solution
{
public:
    int largestRectangleArea(vector<int> &heights) {
     
    }
};

java

class Solution {
    public int largestRectangleArea(int[] heights) {
       
    }
}

python

class Solution:
    def largestRectangleArea(self, heights):

javascript

class Solution {
    largestRectangleArea(heights) {
      
    }
}

csharp

public class Solution
{
    public int LargestRectangleArea(List<int> heights)
    {
     
    }
}

func largestRectangleArea(heights []int) int {

}

Stuck? Show a way to structure it+

01Append an implicit zero-height sentinel.
02Keep indices with increasing heights.
03When a lower bar arrives, pop taller bars.
04Compute width from new stack top to current index.
05Update the best area for each popped bar.

Reference answer

Keep a stack of indices whose heights are nondecreasing. Iterate through all bars plus one virtual trailing bar of height zero, which flushes unfinished rectangles. When the current height is lower than the height at the stack top, pop that index. The popped height is the limiting height of a maximal rectangle ending just before the current index; its left boundary is one after the new stack top, so width is currentIndex minus newTop minus one, or currentIndex if the stack became empty. Update area using poppedHeight times width. Then push the current index. Each index is pushed and popped at most once, so time is O(n) and stack space is O(n). Equal-height handling can use either consistent comparison, but explain your chosen convention. Brute-forcing each bar's expansion is O(n squared).

Then expect these follow-ups

How would you return rectangle boundaries as well as area?
Tests: implementation extension
Why is each stack operation amortized O(1)?
Tests: correctness reasoning

Free to read · better with Enzo

Practice this out loud with Enzo

Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.

Continue with Enzo Sign up free

Next question