Largest Rectangle in Histogram Using Stack in DSA C

Mental Model

We use a stack to keep track of bars that are not yet processed for the largest rectangle. When we find a bar shorter than the top of the stack, we calculate areas for bars that are taller and pop them.

Analogy: Imagine stacking books by height. When a shorter book comes, you remove taller books from the top to find the biggest flat surface you can make with consecutive books.

Histogram bars: heights = [2, 1, 5, 6, 2, 3]
Stack stores indices of bars in increasing height order.

Initial:
Index: 0  1  2  3  4  5
Height:2  1  5  6  2  3
Stack: empty

We push indices while heights increase, pop when current height is less.

Dry Run Walkthrough

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

Goal: Find the largest rectangle area that can be formed in the histogram

Step 1: Push index 0 (height 2) onto stack

Stack: [0]
Heights: 2,1,5,6,2,3

Why: Stack is empty, so push first bar index

Step 2: Current height 1 is less than height at stack top (2), pop index 0 and calculate area

Popped index 0 (height 2), width = current index 1 - stack empty => width=1
Area = 2*1=2
Stack: []

Why: Found a smaller bar, so calculate area for taller bars before it

Step 3: Push index 1 (height 1) onto stack

Stack: [1]
Heights: 2,1,5,6,2,3

Why: Stack empty or current height >= top height, so push

Step 4: Push index 2 (height 5) onto stack

Stack: [1, 2]
Heights: 2,1,5,6,2,3

Why: Current height 5 >= height at top (1), push index 2

Step 5: Push index 3 (height 6) onto stack

Stack: [1, 2, 3]
Heights: 2,1,5,6,2,3

Why: Current height 6 >= height at top (5), push index 3

Step 6: Current height 2 is less than height at stack top (6), pop index 3 and calculate area

Popped index 3 (height 6), width = current index 4 - stack top index 2 - 1 = 1
Area = 6*1=6
Stack: [1, 2]

Why: Smaller bar found, calculate area for taller bars

Step 7: Current height 2 is less than height at stack top (5), pop index 2 and calculate area

Popped index 2 (height 5), width = current index 4 - stack top index 1 - 1 = 2
Area = 5*2=10
Stack: [1]

Why: Continue popping taller bars to find max area

Step 8: Push index 4 (height 2) onto stack

Stack: [1, 4]
Heights: 2,1,5,6,2,3

Why: Current height 2 >= height at top (1), push index 4

Step 9: Push index 5 (height 3) onto stack

Stack: [1, 4, 5]
Heights: 2,1,5,6,2,3

Why: Current height 3 >= height at top (2), push index 5

Step 10: Reached end, pop remaining bars and calculate areas

Pop index 5 (height 3), width = 6 - 4 - 1 = 1, area=3*1=3
Pop index 4 (height 2), width = 6 - 1 - 1 = 4, area=2*4=8
Pop index 1 (height 1), width = 6 - stack empty => width=6, area=1*6=6
Stack empty

Why: Calculate areas for remaining bars to find max

Result:

Largest rectangle area = 10
Final stack empty

Annotated Code

DSA C

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

// Stack structure to hold indices
typedef struct Stack {
    int *arr;
    int top;
    int capacity;
} Stack;

Stack* createStack(int capacity) {
    Stack *stack = (Stack*)malloc(sizeof(Stack));
    stack->capacity = capacity;
    stack->top = -1;
    stack->arr = (int*)malloc(capacity * sizeof(int));
    return stack;
}

int isEmpty(Stack *stack) {
    return stack->top == -1;
}

void push(Stack *stack, int val) {
    stack->arr[++stack->top] = val;
}

int pop(Stack *stack) {
    return stack->arr[stack->top--];
}

int peek(Stack *stack) {
    return stack->arr[stack->top];
}

int largestRectangleArea(int* heights, int heightsSize) {
    Stack *stack = createStack(heightsSize);
    int maxArea = 0;
    int i = 0;

    while (i < heightsSize) {
        // Push index if stack empty or current height >= height at stack top
        if (isEmpty(stack) || heights[i] >= heights[peek(stack)]) {
            push(stack, i);
            i++;
        } else {
            // Pop and calculate area
            int topIndex = pop(stack);
            int width = isEmpty(stack) ? i : i - peek(stack) - 1;
            int area = heights[topIndex] * width;
            if (area > maxArea) maxArea = area;
        }
    }

    // Pop remaining bars
    while (!isEmpty(stack)) {
        int topIndex = pop(stack);
        int width = isEmpty(stack) ? i : i - peek(stack) - 1;
        int area = heights[topIndex] * width;
        if (area > maxArea) maxArea = area;
    }

    free(stack->arr);
    free(stack);
    return maxArea;
}

int main() {
    int heights[] = {2, 1, 5, 6, 2, 3};
    int size = sizeof(heights) / sizeof(heights[0]);
    int result = largestRectangleArea(heights, size);
    printf("Largest rectangle area = %d\n", result);
    return 0;
}

if (isEmpty(stack) || heights[i] >= heights[peek(stack)]) { push(stack, i); i++; }

Push index if current bar is taller or equal to top bar to maintain increasing order

int topIndex = pop(stack); int width = isEmpty(stack) ? i : i - peek(stack) - 1; int area = heights[topIndex] * width; if (area > maxArea) maxArea = area;

Pop taller bar and calculate area with width based on current index and new stack top

while (!isEmpty(stack)) { pop and calculate area similarly for remaining bars }

Calculate area for bars left in stack after processing all bars

Output

Largest rectangle area = 10

Complexity Analysis

Time: O(n) because each bar is pushed and popped at most once

Space: O(n) for the stack that stores indices of bars

vs Alternative: Naive approach checks all pairs for max area with O(n^2) time, stack method is much faster

Edge Cases

Empty histogram

Returns 0 as no bars exist

DSA C

while (i < heightsSize) { ... } handles zero size by skipping loop

All bars same height

Largest rectangle is height * number of bars

DSA C

Push all indices since heights[i] >= heights[peek(stack)] always true

Strictly increasing heights

Stack grows until end, then pops all to calculate max area

DSA C

Push condition keeps adding indices

Strictly decreasing heights

Pop and calculate area at each step as current height is always less

DSA C

Pop condition triggers when current height < top height

When to Use This Pattern

When asked to find largest rectangle area in a histogram or similar structure, use a stack to track bars and calculate areas efficiently by popping when a smaller bar is found.

Common Mistakes

Mistake: Not calculating width correctly when popping from stack
Fix: Width is current index minus stack top index minus one if stack not empty, else current index

Mistake: Forgetting to pop remaining bars after processing all histogram bars
Fix: Add a final loop to pop and calculate area for remaining bars in stack

Summary

Finds the largest rectangle area in a histogram using a stack to track bars.

Use when you need to efficiently find max rectangle area in bar charts or histograms.

The key insight is to use a stack to keep indices of increasing bars and calculate areas when a smaller bar appears.