Largest Rectangle in Histogram

Try to solve the Largest Rectangle in Histogram problem.

We'll cover the following

Statement#

Given an array of integers, heights, that represents the heights of bars in a histogram, find the area of the largest rectangle in the histogram, where the rectangle has a constant width of 11 unit for each bar.

Constraints

  • 1≤1 \leq heights.length ≤103\leq 10^3
  • 0≤0 \leq heights[i] ≤104\leq 10^4

Examples#

canvasAnimation-image

1 of 2

canvasAnimation-image

2 of 2

Understand the problem#

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

Largest Rectangle in Histogram

1

What is the output if the following array of heights is given as input?

heights = [1, 2, 5, 7, 3, 9]

          |-|
          |-|
      |-| |-|
      |-| |-|
    |-|-| |-|
    |-|-| |-|
    |-|-|-|-|
  |-|-|-|-|-|
|-|-|-|-|-|-|
 1 2 5 7 3 9
A)

21

B)

27

C)

10

D)

12

Question 1 of 30 attempted

Try it yourself#

Implement your solution in the following coding playground.

An optimal solution to this problem runs in O(n) time and takes O(n) space.

Python
usercode > main.py
Input #1
%0 node_01 6 node_11 2 node_21 5 node_31 4 node_41 5 node_51 1 node_61 6 node_71 4 node_81 2
Visualization for Input #1
Largest Rectangle in Histogram

You might want to go over the Stacks pattern again.

Solution: Evaluate Reverse Polish Notation

Solution: Largest Rectangle in Histogram