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 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
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.
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
- Shortest Subarray With Sum at Least K Hard Free Find the shortest target-reaching interval when negative values break the usual window.
- Sum of Subarray Minimums Hard Free Add the minimum of every contiguous subarray - by counting, not enumerating.
- Count Bounded Range Sums Hard Free Count signed subarray totals inside an inclusive band without enumerating quadratic pairs.
- Count Inversions Hard Free Count every out-of-order pair without examining every pair.