Skip to main content

100. Largest Rectangle in Histogram

hardAsked at Ola

Find the area of the largest rectangle in a histogram.

By Sam K., 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

More Ola coding interview questions

See all Ola problems →

Companies that also ask Largest Rectangle in Histogram