Skip to main content

24. Largest Rectangle in Histogram

hardAsked at Electronic Arts

Find the largest rectangular area in a histogram using a monotonic stack, testing advanced stack-based spatial reasoning that EA applies in collision-box and physics simulations.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given an array of integers heights representing the histogram's bar heights where the width of each bar is 1, return the area of the largest rectangle in the histogram.

Constraints

  • 1 <= heights.length <= 10^5
  • 0 <= heights[i] <= 10^4

Examples

Example 1

Input
heights = [2,1,5,6,2,3]
Output
10

Example 2

Input
heights = [2,4]
Output
4

Approaches

1. Brute force O(n^2)

For each pair of bars, find the minimum height and compute the area — too slow for large inputs.

Time
O(n^2)
Space
O(1)
function largestRectangleArea(heights) {
  let max = 0;
  for (let i = 0; i < heights.length; i++) {
    let minH = heights[i];
    for (let j = i; j < heights.length; j++) {
      minH = Math.min(minH, heights[j]);
      max = Math.max(max, minH * (j - i + 1));
    }
  }
  return max;
}

Tradeoff:

2. Monotonic increasing stack

Maintain a stack of indices in increasing height order. When a bar shorter than the stack top is encountered, pop and calculate area using the popped bar as the height. Append a sentinel 0 to flush remaining bars at the end.

Time
O(n)
Space
O(n)
function largestRectangleArea(heights) {
  const stack = [-1];
  let max = 0;
  const h = [...heights, 0];
  for (let i = 0; i < h.length; i++) {
    while (stack[stack.length-1] !== -1 && h[stack[stack.length-1]] >= h[i]) {
      const height = h[stack.pop()];
      const width = i - stack[stack.length-1] - 1;
      max = Math.max(max, height * width);
    }
    stack.push(i);
  }
  return max;
}

Tradeoff:

Electronic Arts-specific tips

EA interviews cover game development data structures, pathfinding (A*, BFS on grids), spatial algorithms, and simulation problems. Grid/matrix manipulation and BFS on 2D arrays are very common.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Largest Rectangle in Histogram and other Electronic Arts interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →