Introduction

The Largest Rectangle in Histogram problem involves finding the maximum rectangular area inside a histogram.

Given:

  • array of bar heights

Each bar:

  • width = 1

The task is to:

  • find largest rectangular area
    possible inside histogram

This problem is one of the most important applications of:

 Monotonic Stack

This problem helps in understanding:

  • previous smaller element
  • next smaller element
  • area optimization
  • stack-based traversal

Example

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

Output:
10

Explanation:
Rectangle formed by:
5 and 6
Width = 2
Height = 5
Area = 10

Constraints

1 <= heights.length <= 10^50 <= heights[i] <= 10^4

Approach 1 : Brute Force Expansion

Explanation

The simplest way is:

  1. Take every bar
  2. Expand left and right
  3. Find minimum height region
  4. Calculate maximum area

This works but repeated expansion becomes inefficient.

Steps

  1. Traverse every bar.
  2. Expand left side.
  3. Expand right side.
  4. Calculate area.
  5. Track maximum area.

Dry Run

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

For height 5:

Expand:
5,6
Width = 2
Area = 5 × 2 = 10

Maximum Area:
10

Brute Force Code

Complexity Analysis

Time Complexity: O(n²)Explanation:
Left and right expansions occur repeatedly.

Space Complexity: O(1)
Explanation:
No extra structures used.

Approach 2 : Monotonic Stack

Explanation

The optimized solution uses:

 Monotonic Increasing Stack

Idea:

  • stack stores increasing heights
  • whenever smaller height appears:
    • rectangles are resolved

For each popped bar:

  • current index gives:
    • next smaller element
  • stack top gives:
    • previous smaller element

Area:

height × width

This avoids repeated expansion.

Steps

  1. Create increasing stack.
  2. Traverse histogram.
  3. Resolve taller bars.
  4. Calculate rectangle area.
  5. Track maximum area.

Dry Run

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

Stack:
[]

Push 2
Encounter 1

Pop 2
Width = 1
Area = 2

Push 1
Push 5
Push 6
Encounter 2

Pop 6
Area = 6

Pop 5
Width = 2
Area = 10

Maximum Area:
10

Monotonic Stack Code

Complexity Analysis

Time Complexity: O(n)
Explanation:
Each index is pushed and popped once.

Space Complexity: O(n)
Explanation:
Stack stores indices.

Edge Cases

  1. Single bar
  2. Strictly increasing heights
  3. Strictly decreasing heights
  4. All equal heights
  5. Height = 0

Why This Problem is Important

Largest Rectangle in Histogram helps in understanding:

  1. Monotonic stacks
  2. Previous/next smaller elements
  3. Area optimization
  4. Stack-based geometry problems
  5. Efficient range calculations

It is one of the most important advanced stack interview problems.

Real-World Applications

Histogram optimization concepts are used in:

  1. Image processing
  2. Data visualization
  3. Resource allocation systems
  4. Memory optimization
  5. Skyline analysis

Common Mistakes

  1. Incorrect width calculation
  2. Forgetting final stack cleanup
  3. Wrong stack monotonic order
  4. Missing dummy height at end

Interview Tips

Interviewers often expect:

  1. Monotonic stack explanation
  2. Width calculation reasoning
  3. Previous/next smaller understanding

Always explain:

  • why increasing stack is maintained
  • how width is calculated
  • why each bar is processed once

Related Questions

  1. Trapping Rain Water
  2. Next Greater Element
  3. Daily Temperatures
  4. Maximal Rectangle
  5. Sum of Subarray Minimums

Final Takeaway

The Largest Rectangle in Histogram problem is a fundamental advanced monotonic stack problem that teaches efficient area optimization and previous-next smaller element techniques. Understanding this problem builds a strong foundation for advanced stack and geometry-based interview problems.