22. Matrix Graph Traversal: Number of Islands, Max Area of Island & Clone Graph • Data Structures & Algorithms: Blind 75 & Big Tech Interview Prep • Rishabh Ki Kaksha

Data Structures & Algorithms: Blind 75 & Big Tech Interview Prep › 22. Matrix Graph Traversal: Number of Islands, Max Area of Island & Clone Graph

50 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

# 22. Matrix Graph Traversal: Number of Islands, Max Area of Island & Clone Graph

> DSA Blind 75 Notes by Rishabh - Topic 22

---

### 1. 2D Grid as an Implicit Graph 🏝️

Matrix me har cell $(r, c)$ ek node hota hai jiske 4 neighbors hote hain:
$$\text{Directions: } [(-1, 0), (1, 0), (0, -1), (0, 1)] \text{ (Up, Down, Left, Right)}$$

---

### 2. LeetCode #200: Number of Islands ($O(R \cdot C)$ Flood Fill DFS)

```python
def numIslands(grid: list[list[str]]) -> int:
    if not grid: return 0
    rows, cols = len(grid), len(grid[0])
    islands = 0
    
    def dfs(r, c):
        # Boundary & Water check:
        if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != '1':
            return
            
        grid[r][c] = '0' # 🌊 Sink island in-place to save memory!
        
        dfs(r + 1, c)
        dfs(r - 1, c)
        dfs(r, c + 1)
        dfs(r, c - 1)
        
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                islands += 1
                dfs(r, c) # Sinks the entire connected land
                
    return islands
```

---

### 3. LeetCode #133: Clone Graph ($O(V + E)$ Hash Map DFS)

Deep copy a connected graph where nodes have cycles:

```python
class Node:
    def __init__(self, val = 0, neighbors = None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []

def cloneGraph(node: Node | None) -> Node | None:
    old_to_new = {} # old_node -> cloned_node
    
    def dfs(n):
        if not n: return None
        if n in old_to_new:
            return old_to_new[n]
            
        copy = Node(n.val)
        old_to_new[n] = copy
        for neighbor in n.neighbors:
            copy.neighbors.append(dfs(neighbor))
        return copy
        
    return dfs(node)
```

---

### 4. Master Comparison Matrix

| Problem | Traversal Pattern | Memory Strategy | Time / Space Complexity |
| :--- | :--- | :--- | :--- |
| **Number of Islands** | 4-Directional DFS | In-place sinking (`grid[r][c] = '0'`) | $O(R \cdot C) / O(R \cdot C)$ |
| **Max Area of Island** | DFS returning area `1 + sum(neighbors)` | In-place sinking | $O(R \cdot C) / O(R \cdot C)$ |
| **Pacific Atlantic Water Flow**| Multi-Source BFS/DFS from Oceans | Two Visited Matrices & Intersection | $O(R \cdot C) / O(R \cdot C)$ |

---

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

1. **Pacific Atlantic Water Flow (LeetCode #417) me Ocean boundaries se reverse traverse kyu करते hain?** -> Har individual cell se flow simulate karne me $O((R \cdot C)^2)$ lagta; ocean edges se reverse upward climb karne par $O(R \cdot C)$ me solve ho jata hai.
2. **Rotting Oranges (LeetCode #994) me Multi-Source BFS kyu zaroori hai?** -> Kyunki saare rotten oranges ek sath minute 0 par spread hona shuru karte hain (Single queue initialized with all rotten coords).
3. **Word Search (LeetCode #79) me Backtracking me cell mark karne ke baad revert kyu karte hain?** -> Taaki doosre path explorations ke liye wo cell available rahe (`grid[r][c] = '#' -> explore -> grid[r][c] = original_char`).

---
**Next Topic:** 23. Topological Sort (Kahn's Algorithm): Course Schedule I & II (Cycle Detection)

Loading lesson content...

JavaScript

Live Execution Terminal

Click "Execute Live" to run code.
                