Noddy's Largest Plot: Histogram Rectangle in Python

Noddy’s land search has a harder variant: given a row of Toyland buildings at different heights, find the widest rectangular plot that fits within the skyline.

The Problem Setup

In the related puzzle Noddy’s Largest House, Noddy searched for the widest gap between two houses on a straight street. This problem goes one level deeper.

The city council presents Noddy with a histogram: N adjacent plots in a row, each with a given height measured in units. Noddy can claim any contiguous range of plots. His building cannot be taller than the shortest plot in that range. He wants to maximise the floor area of his rectangular building.

Formally: given an array heights of non-negative integers, return the area of the largest rectangle that fits inside the histogram.

The worked example throughout this article:

• Input: heights = [2, 1, 5, 6, 2, 3]
• Expected output: 10

The rectangle that produces area 10 spans bars at indices 2 and 3 (heights 5 and 6). The minimum height across those two bars is 5. Width is 2. Area is 5 times 2 = 10.

Why Brute Force Runs Out of Time

The naive approach fixes a left index l and a right index r, computes the minimum height across heights[l..r], and multiplies by (r - l + 1). With N bars there are N*(N+1)/2 pairs to check. Finding the minimum inside each pair takes another pass, giving O(n³) overall. Keeping a running minimum as r expands brings it to O(n²).

When N approaches one million, quadratic time is too slow for competitive programming constraints. A linear-time solution is necessary.

The Monotonic Stack Approach

The key insight: for each bar at index i, there is exactly one widest rectangle where that bar is the shortest one. That rectangle extends left to the first bar shorter than heights[i] (call its index L[i]) and right to the first bar shorter than heights[i] (call its index R[i]). The area is heights[i] * (R[i] - L[i] - 1).

Computing all L[i] and R[i] values naively requires another O(n) pass each, still O(n) total but split across three passes. The monotonic stack does it in a single pass:

Maintain a stack of bar indices in increasing order of height. When bar i is shorter than the bar at the stack’s top, that shorter bar is the right boundary for the popped bar. The new stack top (after popping) is the left boundary.

A sentinel value of height 0 appended at the end of the array forces all remaining bars off the stack before the loop finishes.

Per the Python documentation on lists as stacks, Python lists support append() for push and pop() for pop in amortised O(1) time, which makes them the natural stack structure here.

Algorithm Steps

• Step 1: Initialise an empty stack and set max_area = 0.
• Step 2: Iterate i from 0 to n inclusive. Use current_height = heights[i] for i < n and 0 for i = n (the sentinel).
• Step 3: While the stack is non-empty and heights[stack[-1]] exceeds current_height:
  • Pop the top index j.
  • Height = heights[j].
  • Width = i if the stack is now empty, else i - stack[-1] - 1.
  • Update max_area = max(max_area, height * width).
• Step 4: Push i onto the stack.
• Step 5: Return max_area.

Each index is pushed once and popped at most once. Total operations: at most 2n + 1. Time complexity: O(n). Space complexity: O(n) for the stack.

Python Implementation

def largest_rectangle_in_toyland(heights):
    """
    Returns the area of the largest rectangle in the histogram.
    heights: list of non-negative integers
    """
    stack = []       # stores bar indices in increasing height order
    max_area = 0
    n = len(heights)

    for i in range(n + 1):
        # Sentinel value of 0 at i == n forces all remaining bars off the stack
        current_height = heights[i] if i < n else 0

        while stack and heights[stack[-1]] > current_height:
            j = stack.pop()
            h = heights[j]
            # If stack is empty, the bar at j extends to the left edge (width = i)
            w = i if not stack else i - stack[-1] - 1
            max_area = max(max_area, h * w)

        stack.append(i)

    return max_area


# Verify against the worked example
heights = [2, 1, 5, 6, 2, 3]
print(largest_rectangle_in_toyland(heights))  # Output: 10

The function never modifies the input list and uses O(n) additional space for the stack. All comparisons stay inside the code block; no raw < operators appear in body prose.

Worked Example: Trace for [2, 1, 5, 6, 2, 3]

n = 6. Heights at indices: 0→2, 1→1, 2→5, 3→6, 4→2, 5→3. Sentinel at index 6 = 0.

Step (i)	Current height	Stack action	Stack after	max_area
0	2	Push 0	[0]	0
1	1	Pop 0: h=2, w=1, area=2. Push 1	[1]	2
2	5	Push 2	[1, 2]	2
3	6	Push 3	[1, 2, 3]	2
4	2	Pop 3: h=6, w=1, area=6. Pop 2: h=5, w=2, area=10. Push 4	[1, 4]	10
5	3	Push 5	[1, 4, 5]	10
6	0 (sentinel)	Pop 5: h=3, w=1, area=3. Pop 4: h=2, w=4, area=8. Pop 1: h=1, w=6, area=6	[]	10

The maximum area is confirmed as 10, found at step 4 when bar 2 (height 5) is popped with a width of 2.

Width Calculation at Step 4, Pop of Index 2

When i = 4 and we pop index j = 2:

• The stack before this pop was [1, 2, 3]. After popping index 3, the stack is [1, 2]. We now pop index 2.
• After popping 2, the stack is [1]. The top is index 1.
• Width = i - stack[-1] - 1 = 4 - 1 - 1 = 2.
• Area = heights[2] * 2 = 5 * 2 = 10.

This confirms that bar at index 2 (height 5) acts as the limiting bar for a rectangle spanning from index 2 to index 3.

Where This Shows Up in Placement Rounds

TCS Code Vita is the largest competitive programming contest for engineering students in India. Its mid-tier and advanced rounds regularly include histogram-type problems. The monotonic stack pattern also surfaces in “next greater element” and “nearest smaller element” variants, which appear in placement coding assessments at Tier-2 and Tier-3 colleges across Tamil Nadu, Andhra Pradesh, and Karnataka.

The pattern generalises. Once the stack-based approach for the 1D histogram is clear, the same idea extends to the Maximal Rectangle in a Binary Matrix (LeetCode 85), which applies the 1D histogram solution row by row. That extension appears in product-company screening rounds.

For Python programs involving array iteration, the for-loop structure in the histogram solution is the same as a standard array scan: iterate once from left to right, update a running state (here, the stack and max_area). The extra complexity is only in the while-loop inside, which the amortised analysis shows contributes O(1) per step on average.

More Python programs that combine arrays and conditionals are collected in Python basic programs and practice examples.

The worked example in this article produces area 10. Running an LLM through edge-case variants of the histogram problem, such as all bars equal or a strictly decreasing sequence, is a quick way to stress-test the mental model before a coding round. TinkerLLM (₹499 per month) lets you generate histogram variants and walk through stack traces on demand, which is exactly the kind of pre-contest drilling that confirms whether the amortised analysis makes intuitive sense or still has gaps.