Largest Rectangle in Histogram

Largest Rectangle in Histogram is a Hard Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Stack Patterns pattern, in the Largest Rectangle in Histogram subpattern.

Problem statement

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 above is a histogram where width of each bar is 1. The largest rectangle is shown in the red area, which has an area = 10 units.

Example 2:

Input: heights = [2,4] Output: 4

Constraints:

- 1 <= heights.length <= 105

- 0 <= heights[i] <= 104

Topics and companies

Topics: Array, Stack, Monotonic Stack.

Reported in interviews at Amazon, Microsoft, Adobe, MAQ Software.

How to practise Largest Rectangle in Histogram on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n), where n is the number of bars in the histogram. Each bar is pushed and popped from the stack at most once. time and O(n), for the stack used to store indices of the histogram bars. space.

Open Largest Rectangle in Histogram in the code editor, or read the Largest Rectangle in Histogram editorial for a worked solution with its approach and complexity analysis.

Where Largest Rectangle in Histogram sits in the DSA pattern sheet

• Stack Patterns pattern guide
• Largest Rectangle in Histogram subpattern
• The full DSA patterns sheet
• All coding practice problems

Problems related to Largest Rectangle in Histogram

Other problems that use the same Largest Rectangle in Histogram and Stack Patterns techniques:

• Maximal Rectangle — Hard, same subpattern
• Asteroid Collision — Medium, same pattern
• Basic Calculator — Hard, same pattern
• Basic Calculator II — Medium, same pattern
• Basic Calculator III — Hard, same pattern
• Daily Temperatures — Medium, same pattern