Largest Rectangle in Histogram
Given an array of integers heights representing the histogram's bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram.
Example 1:
Input: heights = [2,1,5,6,2,3]
Output: 10
Explanation: The largest rectangle has area = 5 * 2 = 10,
formed by heights[2] = 5 and heights[3] = 6.
┌───┐
│ │
│ ┌─┤
│ │ │ ┌───┐
┌─┤ │ │ ┌───┤ │
│ │ │ │ │ │ │
└─┴─┴─┴─┴───┴───┘
2 1 5 6 2 3
Example 2:
Input: heights = [2,4]
Output: 4
Explanation: The largest rectangle is formed by the single bar heights[1] = 4 with area = 4 * 1 = 4.
Example 3:
Input: heights = [2,1,2]
Output: 3
Explanation: The largest rectangle spans all three bars with height 1, giving area = 1 * 3 = 3.
Examples
Example 1
Input: heights = [2,1,5,6,2,3]
Output: 10
Explanation: The largest rectangle is formed by bars at indices 2 and 3 (heights 5 and 6), giving area = 5 * 2 = 10.
Example 2
Input: heights = [2,4]
Output: 4
Explanation: The single bar at index 1 with height 4 forms the largest rectangle with area = 4 * 1 = 4.
Example 3
Input: heights = [2,1,2]
Output: 3
Explanation: The rectangle spanning all three bars with height 1 gives area = 1 * 3 = 3, which is the largest.
Constraints
- -1 <= heights.length <= 10^5
- -0 <= heights[i] <= 10^4
Optimal Complexity
Time
O(n)
Space
O(n)
Practice this problem with an AI interviewer
TechInView conducts a full voice mock interview — the AI asks clarifying questions, evaluates your approach, watches you code, and scores you on 5 dimensions. Just like a real FAANG interview.
Start a free interview