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

Time Complexity: Largest Rectangle in Histogram Using Stack

O(n)

Understanding Time Complexity

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

How does the algorithm's speed change when the histogram gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

def largest_rectangle_area(heights):
    stack = []
    max_area = 0
    for i, h in enumerate(heights + [0]):
        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
    

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: A single loop goes through each bar once, and inside it, bars are popped from the stack when they are taller than the current bar.
• How many times: Each bar is pushed and popped at most once, so the total number of stack operations is proportional to the number of bars.

How Execution Grows With Input

As the number of bars (n) increases, the algorithm processes each bar a limited number of times.

Input Size (n)	Approx. Operations
10	About 20 stack operations (push and pop combined)
100	About 200 stack operations
1000	About 2000 stack operations

Pattern observation: The number of operations grows roughly in direct proportion to the number of bars.

Final Time Complexity

Time Complexity: O(n)

This means the time to find the largest rectangle grows linearly with the number of bars in the histogram.

Common Mistake

[X] Wrong: "Because there is a nested while loop inside the for loop, the time complexity must be O(n²)."

[OK] Correct: Each bar is pushed and popped only once, so the inner loop does not run for every iteration of the outer loop, keeping the total operations linear.

Interview Connect

Understanding this stack-based approach shows your ability to use data structures smartly to solve problems efficiently, a skill highly valued in coding interviews.

Self-Check

What if we removed the extra 0 added at the end of the heights list? How would the time complexity change?