Largest Rectangle in Histogram - Practice Coding Problems

Largest Rectangle in Histogram - 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.

A rectangle in a histogram is formed by selecting a contiguous range of bars. The height of the rectangle is determined by the shortest bar in that range, and the width is the number of bars in the range.

Your goal is to find the maximum possible area among all such rectangles.

Input & Output

Example 1 — Standard Histogram

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

› Output: 10

💡 Note: The largest rectangle has height 5 and width 2 (indices 2-3), giving area = 5 × 2 = 10

Example 2 — Single Bar

$ Input: heights = [2,4]

› Output: 4

💡 Note: The largest rectangle is the single bar with height 4 and width 1, area = 4 × 1 = 4

Example 3 — Decreasing Heights

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

› Output: 12

💡 Note: Best rectangle uses height 3 spanning 4 bars (indices 0-3), area = 3 × 4 = 12

Constraints

1 ≤ heights.length ≤ 10⁵
0 ≤ heights[i] ≤ 10⁴

Visualization

Tap to expand

Understanding the Visualization

Input Histogram

Array of heights: [2,1,5,6,2,3]

Find Rectangles

Each bar can be minimum height of some rectangle

Maximum Area

Largest rectangle has area 10 (height=5, width=2)

Key Takeaway

🎯 Key Insight: Each bar can be the minimum height of some rectangle - use a monotonic stack to efficiently find the boundaries

Asked in

G Google 45 a Amazon 38 M Microsoft 32 f Facebook 28

The key insight is that each bar can serve as the minimum height of some rectangle. Use a monotonic stack to efficiently find how far each bar can extend left and right. Best approach is the stack solution with Time: O(n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Monotonic Stack	O(n)	O(n)	Use a monotonic increasing stack to efficiently find rectangle boundaries
Brute Force - Check All Subarrays	O(n³)	O(1)	Check every possible rectangle by examining all subarrays

Monotonic Stack — Algorithm Steps

Iterate through heights with stack
Push index if height is increasing
When height decreases, pop and calculate areas
Use popped height as rectangle minimum
Width is between current and previous stack top

Visualization

Tap to expand

Step-by-Step Walkthrough

Push Increasing

Stack: [0,2,3] for heights [2,1,5,6]

Pop When Decreasing

Height 2 < 6, pop index 3 and calculate area

Final Result

Maximum area found: 10

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* heights, int n) {
    int* stack = (int*)malloc(n * sizeof(int));
    int top = -1;
    int maxArea = 0;
    
    for (int i = 0; i < n; i++) {
        while (top >= 0 && heights[i] < heights[stack[top]]) {
            int h = heights[stack[top--]];
            int w = (top < 0) ? i : i - stack[top] - 1;
            int area = h * w;
            if (area > maxArea) maxArea = area;
        }
        stack[++top] = i;
    }
    
    while (top >= 0) {
        int h = heights[stack[top--]];
        int w = (top < 0) ? n : n - stack[top] - 1;
        int area = h * w;
        if (area > maxArea) maxArea = area;
    }
    
    free(stack);
    return maxArea;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int heights[1000];
    int n = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        heights[n++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int result = solution(heights, n);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Each element is pushed and popped from stack exactly once

✓ Linear Growth

Space Complexity

O(n)

Stack can store up to n indices in worst case (increasing heights)

⚡ Linearithmic Space

67.9K Views

High Frequency

~25 min Avg. Time

2.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Monotonic Stack — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler