Design Gurus Logo
Largest Rectangle in Histogram (hard)

Problem Statement

Given an array of integers heights, where heights[i] represents the height of the histogram's bar, return the area of the largest rectangle in the histogram. Each bar has width equal to 1.

Examples

  • Example 1:
    • Input: [4, 2, 3, 2]
Image

  • Expected Output: 8

  • Justification: The largest rectangle can be drawn from the first bar to the fourth bar, having height 2, resulting in an area of 2x4=8.

  • Example 2:

    • Input: [1,3,4,5,2]
Image

  • Expected Output: 9

  • Justification: The largest rectangle can be drawn from the second bar to the fourth bar, having height 3, resulting in an area of 3x3=9.

  • Example 3:

    • Input: [6,2,5,4,5,1,6]
Image
  • Expected Output: 12
  • Justification: The maximum rectangular area is formed by the bars of heights 5, 4, 5, which is equal to 4x3=12. This rectangle spans from the third to the sixth bar.

Try it yourself

Try solving this question here:

Python3
Python3
. . . .

.....

.....

.....

Unlock this and all other premium problems.
No code editor for this lesson
This lesson focuses on concepts and theory