Introduction

The phrase “find the largest area” is too broad to map to one universal algorithm. In programming interviews and algorithm discussions, it most often refers to the largest rectangle in a histogram problem, because that problem has a clear input, a well-known optimal solution, and useful lessons about stacks.

Problem Definition

You are given a list of bar heights. Each bar has width one. The task is to find the largest rectangular area that can be formed using one or more adjacent bars.

For example, with heights [2, 1, 5, 6, 2, 3], the answer is 10, formed by the bars with heights 5 and 6 across width two.

Why the Naive Approach Is Slow

A direct approach is to examine every possible start and end index, compute the minimum height in that range, and calculate the rectangle area. That works, but it is too slow for large inputs because it checks many overlapping ranges repeatedly.

The better solution uses a monotonic stack and runs in linear time.

The Stack Idea

The stack stores indices of bars in non-decreasing height order. When you see a shorter bar, you know the bars taller than it can no longer extend to the right, so you can finalize the largest rectangle for those bars.

For each popped bar:

• its height is the limiting height of a candidate rectangle
• the current index marks the first smaller bar on the right
• the new top of the stack marks the first smaller bar on the left

That gives the full width for which the popped height is the minimum.

Python Implementation

1from typing import List
2
3
4def largest_rectangle_area(heights: List[int]) -> int:
5    stack: List[int] = []
6    best = 0
7    extended = heights + [0]
8
9    for i, h in enumerate(extended):
10        while stack and extended[stack[-1]] > h:
11            height = extended[stack.pop()]
12            left = stack[-1] if stack else -1
13            width = i - left - 1
14            best = max(best, height * width)
15        stack.append(i)
16
17    return best
18
19
20print(largest_rectangle_area([2, 1, 5, 6, 2, 3]))

Output:

10

How the Width Calculation Works

Suppose a bar of height 5 is popped at index 2 when the scan reaches a smaller bar. If the new top of stack is index 1, then the bar at index 2 can extend from index 2 through the position just before the current smaller bar. The width formula is therefore current_index - left_smaller_index - 1.

That -1 is the detail that most incorrect implementations miss.

Why the Extra Zero Helps

The appended zero at the end forces the stack to empty naturally by the time the scan finishes. Without it, you need a second cleanup loop to process the remaining increasing bars.

Both versions are valid, but the sentinel zero makes the code shorter and easier to reason about.

Complexity

Each index is pushed once and popped once, so the total runtime is O(n). The stack uses O(n) extra space in the worst case.

That is a large improvement over the naive quadratic approach and is the reason this solution is the standard answer.

Related “Largest Area” Problems

If your actual problem is different, the right algorithm changes:

• largest rectangle of ones in a binary matrix builds on the histogram algorithm
• largest polygon area uses computational geometry techniques
• largest connected region in a grid uses graph traversal

So before implementing anything, pin down the exact input model. “Largest area” by itself is not a full problem statement.

Common Pitfalls

The most common bug is using bar values instead of indices in the stack. You need indices so you can compute widths correctly.

Another mistake is forgetting to process the remaining bars at the end. Using the sentinel zero or an explicit cleanup loop fixes that.

Developers also often confuse the left boundary after popping. It is not the popped index. It is the index now at the top of the stack, or -1 if the stack is empty.

Summary

• The most common “largest area” algorithmic problem is largest rectangle in a histogram.
• The optimal solution uses a monotonic increasing stack.
• Each popped bar defines a rectangle whose width is bounded by smaller bars on both sides.
• The standard algorithm runs in O(n) time.
• Clarify the exact area problem before coding, because different area tasks require different algorithms.