Largest Rectangle in Histogram
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.
Example 1
Input
6 2 1 5 6 2 3
Output
10
Explanation
The largest rectangle is formed by the bars with heights 5 and 6.
Its height is 5 and width is 2.
Area = 5 × 2 = 10
Example 2
Input
2 2 4
Output
4
Explanation
The largest rectangle is the bar with height 4.
Area = 4 × 1 = 4
Constraints
Hints:
Hint 1
For every bar, determine how far it can extend to the left and right while maintaining its height.
Hint 2
Use a monotonic increasing stack to efficiently find the first smaller bar on both sides.
Author & Technical Reviewer
Technically reviewed by: ExamAdda Technical Review Team
Technical Reviewers, ExamAdda
Software engineers at ExamAdda who check every article's definitions, complexity claims and code examples before and after publishing.
Published
Aug 10, 2026
Last updated
Aug 10, 2026
Content Verification Methodology
Definitions and complexity claims were checked against authoritative computer-science references. Code examples were compiled and tested with standard, boundary and edge-case inputs.
Expected Output