#80 · Stack

Largest Rectangle in Histogram

Given an array of bar heights where each bar has width 1, return the area of the largest rectangle in the histogram.

HardLeetCode

Active
Found
Window
Visited
Rejected

Speed1×step 1 / 1

Pointers

Variables

Hash map / table

Stack / queue

Foundations & data-structure selection

Monotonic (increasing) stack

A stack of indices whose bar heights increase from bottom to top. A new bar pops every taller-or-equal bar: for each popped bar the new bar is the first shorter bar on its right and the bar now on top is the nearest shorter bar on its left.

Memory layout

A contiguous array of at most n + 1 indices with a top pointer.

Operation	Cost
push / pop	O(1)
whole pass	O(n) amortised

Nearest-smaller boundaries

For any bar, the widest rectangle of its own height spans from just after the nearest smaller bar on the left to just before the nearest smaller bar on the right. The answer is the best of these n rectangles.

Memory layout

Two index arrays (left and right limits), or discovered on the fly while popping.

Operation	Cost
per bar	O(1) once limits are known

Why it fits

The optimal rectangle has a shortest bar, and its width is fixed by the nearest shorter bars on either side. So the problem reduces to finding nearest-smaller values for every bar.
A monotonic stack answers "nearest smaller to the left/right" for all positions in a single linear pass.
A sentinel bar of height 0 at the end forces every remaining bar to be popped and measured, removing a second cleanup loop.

Why alternatives degrade

Checking all (i, j) ranges with a running minimum:: O(n²): correct but too slow for 10⁵ bars.
Divide and conquer at the minimum bar:: Finding the minimum needs a range-min structure; without one it degrades to O(n²) on sorted input.
Sorting the bars by height:: Destroys adjacency, which is what defines a rectangle.

Four approaches, from naive to production

1 · beginner

Expand around every bar

time O(n²)space O(1)

For each bar, extend left and right while neighbours are at least as tall, then take height × width. Keep the best.

int largestRectangleArea(vector<int>& heights) {
    int best = 0;
    int n = heights.size();
    for (int i = 0; i < n; i++) {
        int l = i, r = i;
        while (l > 0 && heights[l - 1] >= heights[i]) l--;
        while (r < n - 1 && heights[r + 1] >= heights[i]) r++;
        best = max(best, heights[i] * (r - l + 1));
    }
    return best;
}

public int largestRectangleArea(int[] heights) {
    int best = 0;
    int n = heights.length;
    for (int i = 0; i < n; i++) {
        int l = i, r = i;
        while (l > 0 && heights[l - 1] >= heights[i]) l--;
        while (r < n - 1 && heights[r + 1] >= heights[i]) r++;
        best = Math.max(best, heights[i] * (r - l + 1));
    }
    return best;
}

def largest_rectangle_area(heights):
    best = 0
    n = len(heights)
    for i in range(n):
        l = r = i
        while l > 0 and heights[l - 1] >= heights[i]: l -= 1
        while r < n - 1 and heights[r + 1] >= heights[i]: r += 1
        best = max(best, heights[i] * (r - l + 1))
    return best

function largestRectangleArea(heights: number[]): number {
  let best = 0;
  for (let i = 0; i < heights.length; i++) {
    let l = i, r = i;
    while (l > 0 && heights[l - 1] >= heights[i]) l--;
    while (r < heights.length - 1 && heights[r + 1] >= heights[i]) r++;
    best = Math.max(best, heights[i] * (r - l + 1));
  }
  return best;
}

Flaws & bottlenecks

A sorted (or flat) histogram makes every bar scan the whole array: n² steps.
Rescans the same stretches for neighbouring bars.
Times out on 10⁵ bars.

Interviewer cross-questions

Why is a rectangle bounded by its shortest bar?

Say: Its height cannot exceed the shortest bar it covers, so the best rectangle over any range uses that minimum height.

Why use ≥ when expanding?

Say: Equal bars can be included in the width; excluding them would undercount, though another bar of the same height would still find the full width.

How can you find the boundaries faster?

Say: Nearest smaller element to each side with a monotonic stack, in linear time.

2 · intermediate

Nearest smaller on each side (two stack passes)

time O(n)space O(n)

With a monotonic stack compute, for every bar, the index of the nearest smaller bar on the left and on the right. The rectangle for bar i has width right − left − 1.

int largestRectangleArea(vector<int>& heights) {
    int n = heights.size();
    vector<int> leftLess(n), rightLess(n);
    vector<int> stack;
    for (int i = 0; i < n; i++) {
        while (!stack.empty() && heights[stack.back()] >= heights[i]) stack.pop_back();
        leftLess[i] = stack.empty() ? -1 : stack.back();
        stack.push_back(i);
    }
    stack.clear();
    for (int i = n - 1; i >= 0; i--) {
        while (!stack.empty() && heights[stack.back()] >= heights[i]) stack.pop_back();
        rightLess[i] = stack.empty() ? n : stack.back();
        stack.push_back(i);
    }
    int best = 0;
    for (int i = 0; i < n; i++) best = max(best, heights[i] * (rightLess[i] - leftLess[i] - 1));
    return best;
}

public int largestRectangleArea(int[] heights) {
    int n = heights.length;
    int[] leftLess = new int[n], rightLess = new int[n];
    Deque<Integer> stack = new ArrayDeque<>();
    for (int i = 0; i < n; i++) {
        while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) stack.pop();
        leftLess[i] = stack.isEmpty() ? -1 : stack.peek();
        stack.push(i);
    }
    stack.clear();
    for (int i = n - 1; i >= 0; i--) {
        while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) stack.pop();
        rightLess[i] = stack.isEmpty() ? n : stack.peek();
        stack.push(i);
    }
    int best = 0;
    for (int i = 0; i < n; i++) best = Math.max(best, heights[i] * (rightLess[i] - leftLess[i] - 1));
    return best;
}

def largest_rectangle_area(heights):
    n = len(heights)
    left_less = [0] * n; right_less = [0] * n
    stack = []
    for i in range(n):
        while stack and heights[stack[-1]] >= heights[i]: stack.pop()
        left_less[i] = -1 if not stack else stack[-1]
        stack.append(i)
    stack.clear()
    for i in range(n - 1, -1, -1):
        while stack and heights[stack[-1]] >= heights[i]: stack.pop()
        right_less[i] = n if not stack else stack[-1]
        stack.append(i)
    best = 0
    for i in range(n): best = max(best, heights[i] * (right_less[i] - left_less[i] - 1))
    return best

function largestRectangleArea(heights: number[]): number {
  const n = heights.length;
  const leftLess = new Array<number>(n), rightLess = new Array<number>(n);
  const stack: number[] = [];
  for (let i = 0; i < n; i++) {
    while (stack.length > 0 && heights[stack[stack.length - 1]] >= heights[i]) stack.pop();
    leftLess[i] = stack.length === 0 ? -1 : stack[stack.length - 1];
    stack.push(i);
  }
  stack.length = 0;
  for (let i = n - 1; i >= 0; i--) {
    while (stack.length > 0 && heights[stack[stack.length - 1]] >= heights[i]) stack.pop();
    rightLess[i] = stack.length === 0 ? n : stack[stack.length - 1];
    stack.push(i);
  }
  let best = 0;
  for (let i = 0; i < n; i++) best = Math.max(best, heights[i] * (rightLess[i] - leftLess[i] - 1));
  return best;
}

Flaws & bottlenecks

Three passes and two boundary arrays.
The two directions must use consistent comparisons (≥ on both sides is fine, it just recomputes equal-height rectangles).
Sentinel values (−1 and n) are easy to forget.

Interviewer cross-questions

Why is the stack pass linear?

Say: Each index is pushed once and popped at most once.

What if bars can have equal heights?

Say: Popping on ≥ is fine: the farthest of several equal bars computes the full-width rectangle.

Can both boundaries be found in one pass?

Say: Yes: when a bar is popped, the current bar is its right boundary and the new top is its left boundary.

3 · advanced

One pass: measure a bar when it is popped

time O(n)space O(n)

Scan once with an increasing stack. When a shorter-or-equal bar arrives, pop and compute height × (i − newTop − 1). A virtual bar of height 0 at the end flushes the stack.

int largestRectangleArea(vector<int>& heights) {
    vector<int> stack;
    int best = 0;
    int n = heights.size();
    for (int i = 0; i <= n; i++) {
        int h = (i == n) ? 0 : heights[i];
        while (!stack.empty() && heights[stack.back()] >= h) {
            int height = heights[stack.back()]; stack.pop_back();
            int left = stack.empty() ? -1 : stack.back();
            best = max(best, height * (i - left - 1));
        }
        stack.push_back(i);
    }
    return best;
}

public int largestRectangleArea(int[] heights) {
    Deque<Integer> stack = new ArrayDeque<>();
    int best = 0;
    int n = heights.length;
    for (int i = 0; i <= n; i++) {
        int h = (i == n) ? 0 : heights[i];
        while (!stack.isEmpty() && heights[stack.peek()] >= h) {
            int height = heights[stack.pop()];
            int left = stack.isEmpty() ? -1 : stack.peek();
            best = Math.max(best, height * (i - left - 1));
        }
        stack.push(i);
    }
    return best;
}

def largest_rectangle_area(heights):
    stack = []
    best = 0
    n = len(heights)
    for i in range(n + 1):
        h = 0 if i == n else heights[i]
        while stack and heights[stack[-1]] >= h:
            height = heights[stack.pop()]
            left = stack[-1] if stack else -1
            best = max(best, height * (i - left - 1))
        stack.append(i)
    return best

function largestRectangleArea(heights: number[]): number {
  const stack: number[] = [];
  let best = 0;
  for (let i = 0; i <= heights.length; i++) {
    const h = i === heights.length ? 0 : heights[i];
    while (stack.length > 0 && heights[stack[stack.length - 1]] >= h) {
      const height = heights[stack.pop()!];
      const left = stack.length === 0 ? -1 : stack[stack.length - 1];
      best = Math.max(best, height * (i - left - 1));
    }
    stack.push(i);
  }
  return best;
}

Flaws & bottlenecks

Needs O(n) stack memory (monotonic increasing input keeps every bar).
The sentinel trick is subtle for first-time readers.
Index arithmetic (i − left − 1) is easy to get off by one.

Interviewer cross-questions

Why is the width i − left − 1?

Say: The rectangle spans the bars strictly between the left boundary (the new top) and the right boundary (the current bar).

What is the stack invariant?

Say: Heights strictly increase from bottom to top, so every bar on the stack could still extend to the right.

What does the sentinel do?

Say: The extra bar of height 0 pops everything left on the stack at the end, so no second loop is needed.

4 · expert

Array-backed stack with defensive guards

time O(n)space O(n)

Same algorithm with a preallocated integer array and an integer top pointer. Guard the empty input; use 64-bit areas in languages where height × width could overflow 32 bits.

int largestRectangleArea(vector<int>& heights) {
    int n = heights.size();
    if (n == 0) return 0;
    vector<int> stack(n + 1);
    int top = 0;
    long long best = 0;
    for (int i = 0; i <= n; i++) {
        int h = (i == n) ? 0 : heights[i];
        while (top > 0 && heights[stack[top - 1]] >= h) {
            int height = heights[stack[--top]];
            int left = (top == 0) ? -1 : stack[top - 1];
            best = max(best, (long long)height * (i - left - 1));
        }
        stack[top++] = i;
    }
    return (int)best;
}

public int largestRectangleArea(int[] heights) {
    int n = heights.length;
    if (n == 0) return 0;
    int[] stack = new int[n + 1];
    int top = 0;
    long best = 0;
    for (int i = 0; i <= n; i++) {
        int h = (i == n) ? 0 : heights[i];
        while (top > 0 && heights[stack[top - 1]] >= h) {
            int height = heights[stack[--top]];
            int left = (top == 0) ? -1 : stack[top - 1];
            best = Math.max(best, (long) height * (i - left - 1));
        }
        stack[top++] = i;
    }
    return (int) best;
}

def largest_rectangle_area(heights):
    n = len(heights)
    if n == 0: return 0
    stack = [0] * (n + 1)
    top = 0
    best = 0
    for i in range(n + 1):
        h = 0 if i == n else heights[i]
        while top > 0 and heights[stack[top - 1]] >= h:
            top -= 1
            height = heights[stack[top]]
            left = -1 if top == 0 else stack[top - 1]
            best = max(best, height * (i - left - 1))
        stack[top] = i; top += 1
    return best

function largestRectangleArea(heights: number[]): number {
  const n = heights.length;
  if (n === 0) return 0;
  const stack = new Int32Array(n + 1);
  let top = 0;
  let best = 0;
  for (let i = 0; i <= n; i++) {
    const h = i === n ? 0 : heights[i];
    while (top > 0 && heights[stack[top - 1]] >= h) {
      const height = heights[stack[--top]];
      const left = top === 0 ? -1 : stack[top - 1];
      best = Math.max(best, height * (i - left - 1));
    }
    stack[top++] = i;
  }
  return best;
}

Flaws & bottlenecks

Still O(n) space for the stack (inherent for this method).
In C++/Java the area needs a 64-bit type once heights reach 10⁹ and n is large.
Mutating nothing but trusting that heights are non-negative; negative heights would need validation.

Interviewer cross-questions

Why a typed array instead of a list?

Say: It avoids allocation and resizing and keeps the indices in contiguous memory: faster in hot loops.

What are the edge cases?

Say: Empty input (0), one bar (its height), all bars equal (height × n), strictly increasing and strictly decreasing sequences.

Can this be done with O(1) extra space?

Say: Not with this approach. A sparse table plus divide and conquer uses more; the stack is the practical optimum.

Synchronized code walkthrough

Showing: Expand around every bar — shares the player above; click any step to jump.

int largestRectangleArea(vector<int>& heights) {
    int best = 0;
    int n = heights.size();
    for (int i = 0; i < n; i++) {
        int l = i, r = i;
        while (l > 0 && heights[l - 1] >= heights[i]) l--;
        while (r < n - 1 && heights[r + 1] >= heights[i]) r++;
        best = max(best, heights[i] * (r - l + 1));
    }
    return best;
}

public int largestRectangleArea(int[] heights) {
    int best = 0;
    int n = heights.length;
    for (int i = 0; i < n; i++) {
        int l = i, r = i;
        while (l > 0 && heights[l - 1] >= heights[i]) l--;
        while (r < n - 1 && heights[r + 1] >= heights[i]) r++;
        best = Math.max(best, heights[i] * (r - l + 1));
    }
    return best;
}

def largest_rectangle_area(heights):
    best = 0
    n = len(heights)
    for i in range(n):
        l = r = i
        while l > 0 and heights[l - 1] >= heights[i]: l -= 1
        while r < n - 1 and heights[r + 1] >= heights[i]: r += 1
        best = max(best, heights[i] * (r - l + 1))
    return best

function largestRectangleArea(heights: number[]): number {
  let best = 0;
  for (let i = 0; i < heights.length; i++) {
    let l = i, r = i;
    while (l > 0 && heights[l - 1] >= heights[i]) l--;
    while (r < heights.length - 1 && heights[r + 1] >= heights[i]) r++;
    best = Math.max(best, heights[i] * (r - l + 1));
  }
  return best;
}

int largestRectangleArea(vector<int>& heights) {
    int n = heights.size();
    vector<int> leftLess(n), rightLess(n);
    vector<int> stack;
    for (int i = 0; i < n; i++) {
        while (!stack.empty() && heights[stack.back()] >= heights[i]) stack.pop_back();
        leftLess[i] = stack.empty() ? -1 : stack.back();
        stack.push_back(i);
    }
    stack.clear();
    for (int i = n - 1; i >= 0; i--) {
        while (!stack.empty() && heights[stack.back()] >= heights[i]) stack.pop_back();
        rightLess[i] = stack.empty() ? n : stack.back();
        stack.push_back(i);
    }
    int best = 0;
    for (int i = 0; i < n; i++) best = max(best, heights[i] * (rightLess[i] - leftLess[i] - 1));
    return best;
}

public int largestRectangleArea(int[] heights) {
    int n = heights.length;
    int[] leftLess = new int[n], rightLess = new int[n];
    Deque<Integer> stack = new ArrayDeque<>();
    for (int i = 0; i < n; i++) {
        while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) stack.pop();
        leftLess[i] = stack.isEmpty() ? -1 : stack.peek();
        stack.push(i);
    }
    stack.clear();
    for (int i = n - 1; i >= 0; i--) {
        while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) stack.pop();
        rightLess[i] = stack.isEmpty() ? n : stack.peek();
        stack.push(i);
    }
    int best = 0;
    for (int i = 0; i < n; i++) best = Math.max(best, heights[i] * (rightLess[i] - leftLess[i] - 1));
    return best;
}

def largest_rectangle_area(heights):
    n = len(heights)
    left_less = [0] * n; right_less = [0] * n
    stack = []
    for i in range(n):
        while stack and heights[stack[-1]] >= heights[i]: stack.pop()
        left_less[i] = -1 if not stack else stack[-1]
        stack.append(i)
    stack.clear()
    for i in range(n - 1, -1, -1):
        while stack and heights[stack[-1]] >= heights[i]: stack.pop()
        right_less[i] = n if not stack else stack[-1]
        stack.append(i)
    best = 0
    for i in range(n): best = max(best, heights[i] * (right_less[i] - left_less[i] - 1))
    return best

function largestRectangleArea(heights: number[]): number {
  const n = heights.length;
  const leftLess = new Array<number>(n), rightLess = new Array<number>(n);
  const stack: number[] = [];
  for (let i = 0; i < n; i++) {
    while (stack.length > 0 && heights[stack[stack.length - 1]] >= heights[i]) stack.pop();
    leftLess[i] = stack.length === 0 ? -1 : stack[stack.length - 1];
    stack.push(i);
  }
  stack.length = 0;
  for (let i = n - 1; i >= 0; i--) {
    while (stack.length > 0 && heights[stack[stack.length - 1]] >= heights[i]) stack.pop();
    rightLess[i] = stack.length === 0 ? n : stack[stack.length - 1];
    stack.push(i);
  }
  let best = 0;
  for (let i = 0; i < n; i++) best = Math.max(best, heights[i] * (rightLess[i] - leftLess[i] - 1));
  return best;
}

int largestRectangleArea(vector<int>& heights) {
    vector<int> stack;
    int best = 0;
    int n = heights.size();
    for (int i = 0; i <= n; i++) {
        int h = (i == n) ? 0 : heights[i];
        while (!stack.empty() && heights[stack.back()] >= h) {
            int height = heights[stack.back()]; stack.pop_back();
            int left = stack.empty() ? -1 : stack.back();
            best = max(best, height * (i - left - 1));
        }
        stack.push_back(i);
    }
    return best;
}

public int largestRectangleArea(int[] heights) {
    Deque<Integer> stack = new ArrayDeque<>();
    int best = 0;
    int n = heights.length;
    for (int i = 0; i <= n; i++) {
        int h = (i == n) ? 0 : heights[i];
        while (!stack.isEmpty() && heights[stack.peek()] >= h) {
            int height = heights[stack.pop()];
            int left = stack.isEmpty() ? -1 : stack.peek();
            best = Math.max(best, height * (i - left - 1));
        }
        stack.push(i);
    }
    return best;
}

def largest_rectangle_area(heights):
    stack = []
    best = 0
    n = len(heights)
    for i in range(n + 1):
        h = 0 if i == n else heights[i]
        while stack and heights[stack[-1]] >= h:
            height = heights[stack.pop()]
            left = stack[-1] if stack else -1
            best = max(best, height * (i - left - 1))
        stack.append(i)
    return best

function largestRectangleArea(heights: number[]): number {
  const stack: number[] = [];
  let best = 0;
  for (let i = 0; i <= heights.length; i++) {
    const h = i === heights.length ? 0 : heights[i];
    while (stack.length > 0 && heights[stack[stack.length - 1]] >= h) {
      const height = heights[stack.pop()!];
      const left = stack.length === 0 ? -1 : stack[stack.length - 1];
      best = Math.max(best, height * (i - left - 1));
    }
    stack.push(i);
  }
  return best;
}

int largestRectangleArea(vector<int>& heights) {
    int n = heights.size();
    if (n == 0) return 0;
    vector<int> stack(n + 1);
    int top = 0;
    long long best = 0;
    for (int i = 0; i <= n; i++) {
        int h = (i == n) ? 0 : heights[i];
        while (top > 0 && heights[stack[top - 1]] >= h) {
            int height = heights[stack[--top]];
            int left = (top == 0) ? -1 : stack[top - 1];
            best = max(best, (long long)height * (i - left - 1));
        }
        stack[top++] = i;
    }
    return (int)best;
}

public int largestRectangleArea(int[] heights) {
    int n = heights.length;
    if (n == 0) return 0;
    int[] stack = new int[n + 1];
    int top = 0;
    long best = 0;
    for (int i = 0; i <= n; i++) {
        int h = (i == n) ? 0 : heights[i];
        while (top > 0 && heights[stack[top - 1]] >= h) {
            int height = heights[stack[--top]];
            int left = (top == 0) ? -1 : stack[top - 1];
            best = Math.max(best, (long) height * (i - left - 1));
        }
        stack[top++] = i;
    }
    return (int) best;
}

def largest_rectangle_area(heights):
    n = len(heights)
    if n == 0: return 0
    stack = [0] * (n + 1)
    top = 0
    best = 0
    for i in range(n + 1):
        h = 0 if i == n else heights[i]
        while top > 0 and heights[stack[top - 1]] >= h:
            top -= 1
            height = heights[stack[top]]
            left = -1 if top == 0 else stack[top - 1]
            best = max(best, height * (i - left - 1))
        stack[top] = i; top += 1
    return best

function largestRectangleArea(heights: number[]): number {
  const n = heights.length;
  if (n === 0) return 0;
  const stack = new Int32Array(n + 1);
  let top = 0;
  let best = 0;
  for (let i = 0; i <= n; i++) {
    const h = i === n ? 0 : heights[i];
    while (top > 0 && heights[stack[top - 1]] >= h) {
      const height = heights[stack[--top]];
      const left = top === 0 ? -1 : stack[top - 1];
      best = Math.max(best, height * (i - left - 1));
    }
    stack[top++] = i;
  }
  return best;
}