Largest Rectangle in Histogram

Find the largest rectangle that can be formed in a histogram

Language Selection

Choose your preferred programming language

Showing: Python

Largest Rectangle in Histogram

Problem Statement

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/Output Specifications

  • Input: An array of integers heights where 1 <= heights.length <= 10^5 and 0 <= heights[i] <= 10^4
  • Output: An integer representing the area of the largest rectangle

Constraints

  • 1 <= heights.length <= 10^5
  • 0 <= heights[i] <= 10^4

Examples

Example 1:

Input: heights = [2,1,5,6,2,3]
Output: 10
Explanation: The largest rectangle is formed by bars with heights [5,6], which has area = 5 * 2 = 10.

Example 2:

Input: heights = [2,4]
Output: 4
Explanation: The largest rectangle is formed by the bar with height 4, which has area = 4 * 1 = 4.

Example 3:

Input: heights = [1]
Output: 1

Solution Approaches

Approach 1: Monotonic Stack - Optimal

Algorithm Explanation:

  1. Use a stack to maintain bars in increasing order of height
  2. For each bar, pop bars that are taller than the current bar
  3. Calculate the area of the rectangle formed by the popped bar
  4. The width is determined by the current index and the previous smaller bar

Implementation:

Python:

def largestRectangleArea(heights):
    """
    Find largest rectangle area using monotonic stack
    Time: O(n)
    Space: O(n)
    """
    if not heights:
        return 0
    
    stack = []  # Stack to store indices
    max_area = 0
    
    for i in range(len(heights)):
        # Pop bars that are taller than current bar
        while stack and heights[stack[-1]] > heights[i]:
            height = heights[stack.pop()]
            # Calculate width: current index - previous smaller bar - 1
            width = i - stack[-1] - 1 if stack else i
            max_area = max(max_area, height * width)
        
        stack.append(i)
    
    # Process remaining bars in stack
    while stack:
        height = heights[stack.pop()]
        width = len(heights) - stack[-1] - 1 if stack else len(heights)
        max_area = max(max_area, height * width)
    
    return max_area

Java:

import java.util.*;

class Solution {
    /**
     * Find largest rectangle area using monotonic stack
     * Time: O(n)
     * Space: O(n)
     */
    public int largestRectangleArea(int[] heights) {
        if (heights == null || heights.length == 0) {
            return 0;
        }
        
        Stack<Integer> stack = new Stack<>();
        int maxArea = 0;
        
        for (int i = 0; i < heights.length; i++) {
            // Pop bars that are taller than current bar
            while (!stack.isEmpty() && heights[stack.peek()] > heights[i]) {
                int height = heights[stack.pop()];
                // Calculate width: current index - previous smaller bar - 1
                int width = stack.isEmpty() ? i : i - stack.peek() - 1;
                maxArea = Math.max(maxArea, height * width);
            }
            
            stack.push(i);
        }
        
        // Process remaining bars in stack
        while (!stack.isEmpty()) {
            int height = heights[stack.pop()];
            int width = stack.isEmpty() ? heights.length : heights.length - stack.peek() - 1;
            maxArea = Math.max(maxArea, height * width);
        }
        
        return maxArea;
    }
}

Go:

func largestRectangleArea(heights []int) int {
    /**
     * Find largest rectangle area using monotonic stack
     * Time: O(n)
     * Space: O(n)
     */
    if len(heights) == 0 {
        return 0
    }
    
    var stack []int  // Stack to store indices
    maxArea := 0
    
    for i := 0; i < len(heights); i++ {
        // Pop bars that are taller than current bar
        for len(stack) > 0 && heights[stack[len(stack)-1]] > heights[i] {
            height := heights[stack[len(stack)-1]]
            stack = stack[:len(stack)-1]
            
            // Calculate width: current index - previous smaller bar - 1
            width := i
            if len(stack) > 0 {
                width = i - stack[len(stack)-1] - 1
            }
            maxArea = max(maxArea, height*width)
        }
        
        stack = append(stack, i)
    }
    
    // Process remaining bars in stack
    for len(stack) > 0 {
        height := heights[stack[len(stack)-1]]
        stack = stack[:len(stack)-1]
        
        width := len(heights)
        if len(stack) > 0 {
            width = len(heights) - stack[len(stack)-1] - 1
        }
        maxArea = max(maxArea, height*width)
    }
    
    return maxArea
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

JavaScript:

/**
 * Find largest rectangle area using monotonic stack
 * Time: O(n)
 * Space: O(n)
 */
function largestRectangleArea(heights) {
    if (!heights || heights.length === 0) {
        return 0;
    }
    
    const stack = [];  // Stack to store indices
    let maxArea = 0;
    
    for (let i = 0; i < heights.length; i++) {
        // Pop bars that are taller than current bar
        while (stack.length > 0 && heights[stack[stack.length - 1]] > heights[i]) {
            const height = heights[stack.pop()];
            // Calculate width: current index - previous smaller bar - 1
            const width = stack.length === 0 ? i : i - stack[stack.length - 1] - 1;
            maxArea = Math.max(maxArea, height * width);
        }
        
        stack.push(i);
    }
    
    // Process remaining bars in stack
    while (stack.length > 0) {
        const height = heights[stack.pop()];
        const width = stack.length === 0 ? heights.length : heights.length - stack[stack.length - 1] - 1;
        maxArea = Math.max(maxArea, height * width);
    }
    
    return maxArea;
}

C#:

using System.Collections.Generic;

public class Solution {
    /// <summary>
    /// Find largest rectangle area using monotonic stack
    /// Time: O(n)
    /// Space: O(n)
    /// </summary>
    public int LargestRectangleArea(int[] heights) {
        if (heights == null || heights.Length == 0) {
            return 0;
        }
        
        var stack = new Stack<int>();  // Stack to store indices
        int maxArea = 0;
        
        for (int i = 0; i < heights.Length; i++) {
            // Pop bars that are taller than current bar
            while (stack.Count > 0 && heights[stack.Peek()] > heights[i]) {
                int height = heights[stack.Pop()];
                // Calculate width: current index - previous smaller bar - 1
                int width = stack.Count == 0 ? i : i - stack.Peek() - 1;
                maxArea = Math.Max(maxArea, height * width);
            }
            
            stack.Push(i);
        }
        
        // Process remaining bars in stack
        while (stack.Count > 0) {
            int height = heights[stack.Pop()];
            int width = stack.Count == 0 ? heights.Length : heights.Length - stack.Peek() - 1;
            maxArea = Math.Max(maxArea, height * width);
        }
        
        return maxArea;
    }
}

Complexity Analysis:

  • Time Complexity: O(n) - Each bar is pushed and popped at most once
  • Space Complexity: O(n) - Stack can store at most n elements

Approach 2: Brute Force

Algorithm Explanation:

  1. For each bar, find the largest rectangle that can be formed with this bar as the minimum height
  2. Expand left and right to find the boundaries
  3. Calculate the area for each possible rectangle

Implementation:

Python:

def largestRectangleArea_brute(heights):
    """
    Find largest rectangle area using brute force
    Time: O(n^2)
    Space: O(1)
    """
    if not heights:
        return 0
    
    max_area = 0
    
    for i in range(len(heights)):
        # Find left boundary
        left = i
        while left >= 0 and heights[left] >= heights[i]:
            left -= 1
        
        # Find right boundary
        right = i
        while right < len(heights) and heights[right] >= heights[i]:
            right += 1
        
        # Calculate area
        width = right - left - 1
        area = heights[i] * width
        max_area = max(max_area, area)
    
    return max_area

Complexity Analysis:

  • Time Complexity: O(n^2) - For each bar, potentially scan all other bars
  • Space Complexity: O(1) - Only using constant extra space

Key Insights

  1. Monotonic Stack: Maintain bars in increasing order of height
  2. Area Calculation: Width is determined by the boundaries of the rectangle
  3. Boundary Finding: Use stack to efficiently find previous smaller elements
  4. Remaining Elements: Process remaining elements in stack after main loop

Edge Cases

  1. Empty Array: Return 0
  2. Single Element: Return the height of the single bar
  3. Increasing Heights: All bars in increasing order
  4. Decreasing Heights: All bars in decreasing order
  5. Equal Heights: Multiple bars with the same height

Test Cases

def test_largestRectangleArea():
    # Test case 1
    heights1 = [2,1,5,6,2,3]
    assert largestRectangleArea(heights1) == 10
    
    # Test case 2
    heights2 = [2,4]
    assert largestRectangleArea(heights2) == 4
    
    # Test case 3
    heights3 = [1]
    assert largestRectangleArea(heights3) == 1
    
    # Test case 4
    heights4 = [1,1,1,1]
    assert largestRectangleArea(heights4) == 4
    
    # Test case 5
    heights5 = [5,4,3,2,1]
    assert largestRectangleArea(heights5) == 9
    
    print("All tests passed!")

test_largestRectangleArea()

Follow-up Questions

  1. Largest Rectangle in 2D: Find largest rectangle in a 2D matrix?
  2. Largest Square: Find largest square instead of rectangle?
  3. Multiple Histograms: Handle multiple histograms?
  4. Dynamic Updates: Handle dynamic updates to heights?
  5. Optimization: Optimize for specific patterns?

Common Mistakes

  1. Wrong Stack Order: Not maintaining monotonic stack correctly
  2. Width Calculation: Incorrect width calculation
  3. Boundary Handling: Not handling stack empty cases
  4. Remaining Elements: Not processing remaining elements in stack
  5. Index Management: Off-by-one errors in index calculations

Interview Tips

  1. Start with Brute Force: Show understanding of the problem
  2. Optimize with Stack: Explain the monotonic stack approach
  3. Discuss Trade-offs: Compare time and space complexities
  4. Handle Edge Cases: Cover empty array and special cases
  5. Code Carefully: Pay attention to stack operations and width calculations

Concept Explanations

Monotonic Stack: A stack that maintains elements in a specific order (increasing or decreasing). For this problem, we maintain increasing order to efficiently find previous smaller elements.

Histogram: A graphical representation of data using bars of different heights. In this problem, each bar represents a height value.

Rectangle Area: The area of a rectangle is calculated as width × height. For a histogram bar, the height is the bar’s value, and the width is determined by the boundaries.

When to Use: Use this pattern when you need to find the largest rectangle, maximum area, or when dealing with problems involving finding boundaries or previous/next smaller elements.