Largest Rectangle in Histogram Using Stack in DSA C - Time & Space Complexity

Time Complexity: Largest Rectangle in Histogram Using Stack

O(n)

Understanding Time Complexity

We want to know how the time needed to find the largest rectangle in a histogram changes as the number of bars grows.

How does the algorithm's work increase when the histogram gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

int largestRectangleArea(int* heights, int heightsSize) {
    int maxArea = 0;
    int stack[heightsSize];
    int top = -1;
    for (int i = 0; i <= heightsSize; i++) {
        int h = (i == heightsSize) ? 0 : heights[i];
        while (top != -1 && h < heights[stack[top]]) {
            int height = heights[stack[top--]];
            int width = (top == -1) ? i : i - stack[top] - 1;
            int area = height * width;
            if (area > maxArea) maxArea = area;
        }
        stack[++top] = i;
    }
    return maxArea;
}
    

This code finds the largest rectangle area in a histogram by using a stack to track bars and calculate areas efficiently.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The for-loop runs through each bar once, and the while-loop pops bars from the stack when the current bar is smaller.
• How many times: Each bar is pushed and popped at most once, so total operations related to bars happen about 2n times.

How Execution Grows With Input

As the number of bars (n) increases, the total steps grow roughly twice as fast because each bar is pushed and popped once.

Input Size (n)	Approx. Operations
10	About 20 operations
100	About 200 operations
1000	About 2000 operations

Pattern observation: The operations grow linearly with input size, doubling roughly because of push and pop actions.

Final Time Complexity

Time Complexity: O(n)

This means the time to find the largest rectangle grows directly in proportion to the number of bars.

Common Mistake

[X] Wrong: "The nested while-loop makes this algorithm O(n²) because it looks like loops inside loops."

[OK] Correct: Each bar is pushed and popped only once, so the total work inside the while-loop across the whole run is still proportional to n, not n squared.

Interview Connect

Understanding this stack-based approach shows you can use clever data structures to reduce work and improve efficiency, a key skill in problem solving.

Self-Check

"What if we used a simple nested loop checking all pairs instead of a stack? How would the time complexity change?"