Largest Rectangle in Histogram — Hard Coding Interview Question

Given an array of integers heights representing a histogram's bar heights where each bar has width 1, return the area of the largest rectangle in the histogram.

Example

Input: heights = [2,1,5,6,2,3]

Output: 10

Explanation: Formed by heights 5 and 6 with width 2.

Constraints

• 1 ≤ heights.length ≤ 10⁵
• 0 ≤ heights[i] ≤ 10⁴

Topics & Companies

Topics: stack, arrays

Asked by: Amazon, Google, Meta, Microsoft

Optimal Solution Complexity

Time complexity: O(n). Space complexity: O(n).

Practice more

• All DSA Problems
• DSA Patterns