Skip to content
Katabench
Try free

Largest Rectangle in Histogram

Hard About 35 min Free, no account needed

The biggest rectangle that fits under the bars.

The brief

Given heights, the bar heights of a histogram (bar width 1), return the area of the largest rectangle that fits entirely under the bars.

The performance bar

The obvious approach grows each bar's rectangle outward while neighbors are tall enough, O(n2), and the hidden test is 100,000 equal bars where every extension spans the whole histogram, so it's too slow. You will need a solution that runs in O(n).

Starter code

C#
using System;

public class Solution
{
    // TODO: return the area of the largest rectangle under the histogram bars.
    public long LargestRectangle(int[] heights)
    {
        throw new NotImplementedException();
    }
}

How it is graded

Visible examples help you iterate. Hidden tests then cover edge cases and larger inputs, and every test reports server-measured time and allocated bytes.

C# coding challenges →

What it practices

Monotonic stack
Keep a stack in sorted order to answer next-greater and span questions in one pass.

Do these first

Related katas