Skip to main content

100. Largest Rectangle in Histogram

hardAsked at Ola

Find the area of the largest rectangle in a histogram.

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 pairs

Try every (i, j) pair; take min height times width.

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

Tradeoff:

2. Monotonic stack

Push indices while bars are non-decreasing; pop and compute area when a shorter bar arrives. O(n) amortized.

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

Tradeoff:

Ola-specific tips

Ola interviewers ask the monotonic stack as a senior-IC signal; tie it to finding the widest contiguous time-block where supply stays above a threshold.

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 Ola interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →