13. Hard Stack Coding: Largest Rectangle in Histogram & Trapping Rain Water • Data Structures & Algorithms: Blind 75 & Big Tech Interview Prep • Rishabh Ki Kaksha

Data Structures & Algorithms: Blind 75 & Big Tech Interview Prep › 13. Hard Stack Coding: Largest Rectangle in Histogram & Trapping Rain Water

55 mins

← Prev Next →

Course Syllabus

Module 1: Big-O Asymptotics, Arrays & Sliding Window

01. Time & Space Complexity Masterclass: Big-O, Big-Theta, Big-Omega & Amortized Analysis 02. Arrays & Hashing: Two Sum, Contains Duplicate & Valid Anagram (Hash Table Lookups) 03. Prefix Sum & Kadane's Algorithm (Maximum Subarray Problem in O(N)) 04. Sliding Window Pattern: Fixed vs Dynamic Windows (Best Time to Buy/Sell Stock)

Module 2: Two Pointers & Binary Search Systems

05. Two Pointers Pattern: Valid Palindrome, 3Sum & Container With Most Water 06. Binary Search Foundations: Search in Rotated Sorted Array & Find Minimum 07. Binary Search on Answer Space: Koko Eating Bananas & Capacity to Ship Packages

Module 3: Linked Lists & Fast-Slow Pointer Patterns

08. Singly vs Doubly Linked Lists & In-Place Pointer Manipulation (Reverse Linked List) 09. Fast & Slow Pointer (Floyd's Cycle Detection): Linked List Cycle & Middle Node 10. Merging & Reordering: Merge Two Sorted Lists, Reorder List & Remove Nth Node

Module 4: Stacks, Queues & Monotonic Stack Architecture

11. Stack Fundamentals: Valid Parentheses & Min Stack in O(1) Time 12. Monotonic Stack Pattern: Daily Temperatures & Next Greater Element 13. Hard Stack Coding: Largest Rectangle in Histogram & Trapping Rain Water

Module 5: Trees, Binary Search Trees & DFS/BFS Traversals

14. Binary Tree Architecture: Max Depth, Same Tree & Invert Binary Tree 15. BFS Level-Order Traversal & Binary Tree Right Side View 16. Binary Search Tree (BST) Properties: Validate BST & Lowest Common Ancestor (LCA) 17. Tree Path Sums & Serialize / Deserialize Binary Tree (Hard)

Module 6: Heaps, Priority Queues & Top-K Problems

18. Min Heap & Max Heap Internals: Array Representation & Heapify in O(N) 19. Top-K Elements Pattern: Kth Largest Element in an Array & Top K Frequent Elements 20. Two-Heap Pattern: Find Median from Data Stream (Hard)

Module 7: Graphs, Topological Sort & Shortest Paths (Dijkstra)

21. Graph Representations (Adjacency Matrix vs List) & DFS/BFS Traversal 22. Matrix Graph Traversal: Number of Islands, Max Area of Island & Clone Graph 23. Topological Sort (Kahn's Algorithm): Course Schedule I & II (Cycle Detection) 24. Disjoint Set Union (DSU / Union-Find): Redundant Connection & Number of Connected Components

Module 8: Dynamic Programming, Backtracking & Bit Manipulation

25. Backtracking Pattern: Subsets, Permutations, Combination Sum & Word Search 26. 1D Dynamic Programming: Climbing Stairs, House Robber & Coin Change 27. Longest Increasing Subsequence (LIS): O(N^2) DP vs O(N log N) Patience Sort 28. 2D Dynamic Programming: Unique Paths, Longest Common Subsequence (LCS) & Edit Distance 29. 0/1 Knapsack Pattern & Partition Equal Subset Sum 30. Bit Manipulation Tricks: Number of 1 Bits (Hamming Weight), Counting Bits & Missing Number

Interactive Lesson Studio

# 13. Hard Stack Coding: Largest Rectangle in Histogram & Trapping Rain Water

> DSA Blind 75 Notes by Rishabh - Topic 13

---

### 1. LeetCode #84: Largest Rectangle in Histogram ($O(N)$ Monotonic Stack)

*Problem:* Histogram bars se banne wale sabse bade rectangle ka area calculate karo.

```python
def largestRectangleArea(heights: list[int]) -> int:
    stack = [] # (index, height)
    max_area = 0
    
    for i, h in enumerate(heights):
        start = i
        while stack and stack[-1][1] > h:
            index, height = stack.pop()
            max_area = max(max_area, height * (i - index))
            start = index # Rectangle can extend backwards to popped index!
        stack.append((start, h))
        
    for index, height in stack:
        max_area = max(max_area, height * (len(heights) - index))
        
    return max_area
```

---

### 2. LeetCode #42: Trapping Rain Water ($O(N)$ Two Pointers / Stack)

*Formula:* Har position par kitna paani rukega:
$$\text{Water}[i] = \max(0, \min(\text{max\_left}, \text{max\_right}) - \text{height}[i])$$

```python
def trap(height: list[int]) -> int:
    if not height: return 0
    left, right = 0, len(height) - 1
    left_max, right_max = height[left], height[right]
    water = 0
    
    while left < right:
        if left_max < right_max:
            left += 1
            left_max = max(left_max, height[left])
            water += left_max - height[left]
        else:
            right -= 1
            right_max = max(right_max, height[right])
            water += right_max - height[right]
            
    return water
```
*Time Complexity:* $O(N)$, *Space Complexity:* $O(1)$.

---

### 3. Master Comparison Matrix

| Problem | Approach 1 (DP / Array) | Approach 2 (Optimal) | Complexity |
| :--- | :--- | :--- | :--- |
| **Largest Rectangle in Histogram**| Divide & Conquer $O(N \log N)$ | **Monotonic Stack $O(N)$** | $O(N) / O(N)$ |
| **Maximal Rectangle (2D Matrix)** | Run LC 84 on each row | **2D Histogram Reduction** | $O(R \cdot C)$ |
| **Trapping Rain Water** | Left/Right Max Arrays $O(N)$ space | **Two Pointers $O(1)$ space** | $O(N) / O(1)$ |

---

### 4. Interview Ke 3 Sawal Is Topic Se

1. **Maximal Rectangle in 2D Binary Matrix (LeetCode #85) LC #84 se kaise solve hota hai?** -> Har row ko baseline mankar consecutive 1s ko histogram bars bana lete hain aur har row par Largest Rectangle in Histogram function call karte hain.
2. **Trapping Rain Water me Two Pointers me chhota max kyu move karte hain?** -> Kyunki bottleneck hamesha smaller boundary hoti hai; agar `left_max < right_max`, toh right side chahe kitni bhi unchi ho, water level `left_max` se decide hoga.
3. **Asteroid Collision (LeetCode #735) me stack handling kaise hoti hai?** -> Positive asteroids right move karte hain aur negative left; collision sirf tab hota hai jab stack ke top par positive ho aur incoming negative ho.

---
**Next Topic:** 14. Binary Tree Architecture: Max Depth, Same Tree & Invert Binary Tree

Loading lesson content...

JavaScript

Live Execution Terminal

Click "Execute Live" to run code.
                