AlgoMonster: The Most Structured Way to Prepare for Coding Interviews

Largest Rectangle in Histogram

Hard

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

Example:

Input: heights = [2,1,5,6,2,3]
Output: 10
Explanation: The largest rectangle is formed by heights [5,6] with width 2 (5*2=10).

Input: heights = [2,4]
Output: 4
Explanation: The largest rectangle is formed by the single bar of height 4.

Test Cases

Input

3 5 6 2 1 4

Expected Output

Step 1

Step 2

Step 3

Step 4

Step 1: Identify the Pattern

Brute Force1

Monotonic Stack2

Divide and Conquer3

Dynamic Programming4

Largest Rectangle in Histogram

Hard

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

Example:

Input: heights = [2,1,5,6,2,3]
Output: 10
Explanation: The largest rectangle is formed by heights [5,6] with width 2 (5*2=10).

Input: heights = [2,4]
Output: 4
Explanation: The largest rectangle is formed by the single bar of height 4.

Test Cases

Input

3 5 6 2 1 4

Expected Output

Step 1

Step 2

Step 3

Step 4

Step 1: Identify the Pattern

Brute Force1

Monotonic Stack2

Divide and Conquer3

Dynamic Programming4

Example:

Test Cases

Example:

Test Cases

Study Notes

Start Taking Notes!