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)
Choose between solo practice and interview simulation
Practice Mode keeps things simple with code + tests. AI Interview Mode adds voice, pressure, and a post-round score summary.