Largest Rectangle in a Histogram
Updated
Problem statement
The array heights describes adjacent histogram bars. Every bar has width 1, and heights[i] is its nonnegative integer height.
Choose one or more consecutive bars and draw a rectangle resting on the baseline that fits entirely beneath those bars. Its height cannot exceed the smallest bar in the chosen interval.
Return the largest possible rectangle area. Bars of height 0 are allowed; an all-zero histogram has area 0.
Function
largestRectangleArea(heights: int[]) → intExamples
Example 1
heights = [2,1,5,6,2,3]return = 10Bars at indices 2 and 3 support height 5 over width 2, giving area 10. No contiguous interval supports a larger area.
Example 2
heights = [2,4]return = 4The first bar alone has area 2, the second has area 4, and both together support height 2 over width 2. The maximum is 4.
Example 3
heights = [0,0]return = 0Every possible rectangle has height 0, so the maximum area is 0.
Constraints
1 <= heights.length <= 100000.0 <= heights[i] <= 10000.
More Decagon Phone Screen questions
- Count Complete Tic-Tac-Toe GamesPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Rolling CSAT TrackerPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Batch API Requests with Retry DelaysPHONE SCREEN · Seen Sep 2026
- Recipe Cart with Undo and RedoPHONE SCREEN · Seen Sep 2026
- Recipe Shopping Cart DiscountsPHONE SCREEN · Seen Aug 2026
- Versioned Recipe Shopping CartPHONE SCREEN · Seen Jul 2026
- Nested Recipe Cart TransactionsPHONE SCREEN · Seen Jul 2026
- Count Hits in the Last Five MinutesPHONE SCREEN · Seen Apr 2026
- Exclusive Function Execution TimePHONE SCREEN · Seen Mar 2026
Similar questions at other companies
- Trapping Rain WaterBloomberg LP · PHONE SCREEN · ONSITE INTERVIEWBloomberg LP interview questions
- Count Visible People to the LeftGoogle · PHONE SCREEN · ONSITE INTERVIEWGoogle interview questions
- Trapping Rain WaterAmazon · PHONE SCREEN · ONSITE INTERVIEW
- Confirmed Profiling Events with First-Observed StartsAnthropic · PHONE SCREEN · ONSITE INTERVIEWAnthropic interview questions
- Largest Rectangle in HistogramAirwallex · PHONE SCREENAirwallex interview questions
- Rain Kept Between WallsDocuSign · PHONE SCREENDocuSign interview questions
- Rain Water Held Between BarsAdobe · PHONE SCREENAdobe interview questions
- Asteroid CollisionSiemens · PHONE SCREEN
- Billing Log with Undo and RedoReddit · PHONE SCREENReddit interview questions
- Next Taller Building to the RightTemu · PHONE SCREENTemu interview questions