How to Solve: Largest Rectangle in Histogram

How to Solve: Largest Rectangle in Histogram

(Complete Guide for FAANG-Level Interviews)

? Introduction

"This problem separates candidates who ‘know’ algorithms from those who can apply them under pressure. It’s a staple in Google, Meta, and Amazon onsites—master it, and you prove you can optimize brute-force solutions into linear time using stacks, a skill that directly translates to real-world system design."

? WHAT YOU NEED TO KNOW FIRST

Before tackling this problem, ensure you’re fluent in: 1. Stacks (LIFO) – How to push/pop and track indices. 2. Monotonic Stacks – Maintaining a stack where elements are in increasing/decreasing order. 3. Time Complexity Analysis – Recognizing O(n²) vs. O(n) trade-offs.

? KEY TECHNIQUES & PATTERNS

? STEP-BY-STEP FRAMEWORK

Mental Checklist (Run This for Every Histogram Problem):

1. Clarify Input/Output
2. Input: Array of integers heights (non-negative).

3. Output: Integer (max area of a rectangle under the histogram).

4. Brute-Force Intuition

5. For each bar, treat it as the smallest bar in a rectangle.
6. Expand left/right to find the widest possible rectangle.

7. Time: O(n²) → Too slow for large inputs (n > 10⁴).

8. Optimize with Monotonic Stack

9. Initialize an empty stack and max_area = 0.
10. Iterate through heights + a sentinel 0 (to force stack cleanup).
11. While current bar’s height < stack’s top bar’s height:
    • Pop the stack → calculate area with popped bar as the smallest bar.
    • Update max_area if larger.

12. Push current bar’s index onto the stack.

13. Calculate Width Correctly

14. For a popped bar at index i with height h:

    • width = current_index - stack[-1] - 1 (if stack not empty).
    • Else, width = current_index (no smaller bar to the left).

15. Edge Cases

16. Empty input → return 0.
17. Single bar → return its height.

18. All bars same height → return n height.

19. Time/Space Complexity

20. Time: O(n) (each bar pushed/popped once).
21. Space: O(n) (stack storage).

? WORKED EXAMPLES

Example 1 – Basic (LeetCode 84)

Input: heights = [2, 1, 5, 6, 2, 3] Output: 10 (Rectangle formed by bars of height 5 and 6).

Step-by-Step Walkthrough

1. Initialize stack = [], max_area = 0.
2. Iterate with i = 0 to 6 (sentinel 0 at i=6):
3. i=0: Push 0 (stack = [0]).
4. i=1: heights[1] = 1 < heights[0] = 2 → Pop 0:
   • height = 2, width = 1 - (-1) - 1 = 1 (stack empty after pop).
   • area = 2 1 = 2 → max_area = 2.
5. Push 1 (stack = [1]).
6. i=2: Push 2 (stack = [1, 2]).
7. i=3: Push 3 (stack = [1, 2, 3]).
8. i=4: heights[4] = 2 < heights[3] = 6 → Pop 3:
   • height = 6, width = 4 - 2 - 1 = 1.
   • area = 6 1 = 6 → max_area = 6.
9. heights[4] = 2 < heights[2] = 5 → Pop 2:
   • height = 5, width = 4 - 1 - 1 = 2.
   • area = 5 2 = 10 → max_area = 10.
10. Push 4 (stack = [1, 4]).
11. i=5: Push 5 (stack = [1, 4, 5]).
12. i=6 (sentinel 0):
    • Pop 5 → area = 3 (6 - 4 - 1) = 3 → max_area unchanged.
    • Pop 4 → area = 2 (6 - 1 - 1) = 8 → max_area = 10.
    • Pop 1 → area = 1 6 = 6 → max_area unchanged.

Python Code

def largestRectangleArea(heights):

    stack = []

    max_area = 0

    heights.append(0)  # Sentinel

    for i, h in enumerate(heights):

        while stack and heights[stack[-1]] > h:

            height = heights[stack.pop()]

            width = i if not stack else i - stack[-1] - 1

            max_area = max(max_area, height  width)

        stack.append(i)

    return max_area

Why This Works

• The stack maintains indices of bars in increasing order.
• When a smaller bar is encountered, we pop and calculate the area of rectangles where the popped bar is the smallest.
• The sentinel 0 ensures all bars are processed.

Example 2 – Medium (All Bars Same Height)

Input: heights = [3, 3, 3, 3] Output: 12 (Entire histogram is a rectangle).

Key Insight

• The stack will only pop when the sentinel 0 is encountered.
• All bars are processed at once, with width = n.

Python Code

def largestRectangleArea(heights):

    stack = []

    max_area = 0

    heights.append(0)

    for i, h in enumerate(heights):

        while stack and heights[stack[-1]] > h:

            height = heights[stack.pop()]

            width = i if not stack else i - stack[-1] - 1

            max_area = max(max_area, height  width)

        stack.append(i)

    return max_area

Output: 12 (4 bars × height 3).

Example 3 – Hard (Follow-Up: Maximal Rectangle in Binary Matrix)

Problem: Given a rows x cols binary matrix, find the largest rectangle containing only 1s. LeetCode: 85 (Follow-up to Histogram problem).

Approach

1. Treat each row as the base of a histogram.
2. For each row, update the histogram heights:
3. If matrix[i][j] == '1', heights[j] += 1.
4. Else, heights[j] = 0.
5. Apply the histogram solution to each row’s heights.

Python Code

def maximalRectangle(matrix):

    if not matrix:

        return 0

    rows, cols = len(matrix), len(matrix[0])

    heights = [0]  cols

    max_area = 0

    for i in range(rows):

        for j in range(cols):

            heights[j] = heights[j] + 1 if matrix[i][j] == '1' else 0

        stack = []

        heights.append(0)

        for k, h in enumerate(heights):

            while stack and heights[stack[-1]] > h:

                height = heights[stack.pop()]

                width = k if not stack else k - stack[-1] - 1

                max_area = max(max_area, height  width)

            stack.append(k)

        heights.pop()  # Remove sentinel

    return max_area

Why This Works

• The histogram solution is applied row-wise, leveraging dynamic height updates.
• Time: O(rows × cols) (each cell processed once).

❌ Common Mistakes

? INTERVIEW TrapS

? 1-Minute Recap

"Here’s your 60-second cheat sheet for ‘Largest Rectangle in Histogram’: 1. Brute-force is O(n²)—too slow. You need O(n). 2. Use a monotonic stack to track indices of bars in increasing order. 3. Append a sentinel 0 to force the stack to empty at the end. 4. When popping, calculate area as height × width, where width = current_index - stack[-1] - 1. 5. Edge cases: Empty input, single bar, all bars same height. 6. Follow-up: For 2D matrices, treat each row as a histogram and reuse the stack solution.

Walk in confident—you’ve got this!

? Final Notes

• Practice: LeetCode 84 (Histogram), 85 (Matrix).
• Whiteboard: Draw the stack state at each step for [2, 1, 5, 6, 2, 3].
• Time: Aim for <15 minutes in an interview.

This framework is directly transferable to other monotonic stack problems (e.g., "Next Greater Element"). Good luck! ?