Number of Islands

• Difficulty: Medium
• Topics: Array, Depth-First Search, Breadth-First Search, Union Find, Matrix
• Link: https://leetcode.com/problems/number-of-islands/

Problem Description

Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.

An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:

Input: grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
Output: 1

Example 2:

Input: grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
Output: 3

Constraints:

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 300
• grid[i][j] is '0' or '1'.

Solution

1. Problem Deconstruction

Technical Description:
Given an m × n 2D binary grid grid where '1' represents land and '0' represents water, compute the number of connected components (islands) formed by horizontally or vertically adjacent '1's. The grid boundaries are surrounded by water.

Beginner Description:
Imagine a map with land (1) and water (0). An island is a group of lands touching each other directly (up, down, left, or right—not diagonally). Your task is to count all such separate groups. For example:

• A map with one big land mass → 1 island.
• A map with three separate clusters → 3 islands.

Mathematical Formalization:

• Define the grid as a matrix ( G ) of size ( m \times n ), where ( G_{i,j} \in {0, 1} ).
• Construct a graph ( \mathcal{G} = (V, E) ):
  • ( V = {(i, j) \mid G_{i,j} = 1} ) (land cells).
  • ( E = {((i, j), (i’, j’)) \mid |i - i’| + |j - j’| = 1} ) (horizontal/vertical adjacency).
• The solution is the number of connected components in ( \mathcal{G} ).

---

Constraint Analysis:

• Grid Dimensions:
  • ( 1 \leq m, n \leq 300 ): Total cells ( \leq 90,000 ). Allows ( O(mn) ) solutions.
• Binary Values:
  • ( G_{i,j} ) is '0' or '1' → No invalid inputs.
• Edge Cases:
  • All '0's → 0 islands.
  • All '1's → 1 island.
  • Single '1' → 1 island.
  • Diagonal lands (e.g., [[1,0],[0,1]]) → 2 islands (not connected).

---

2. Intuition Scaffolding

Analogies:

1. Real-World Metaphor:
   • Like counting continents on Earth—each contiguous landmass (ignoring diagonals) is one island.
2. Gaming Analogy:
   • In a strategy game, each “territory” (connected land) counts as one region. Scouting marks all adjacent lands.
3. Math Analogy:
   • Equivalent to counting connected components in a graph defined by 4-directional adjacency.

Common Pitfalls:

1. Unmarked Visits:
   • Recounting the same island by not marking visited cells.
2. Stack Overflow:
   • Using DFS recursion for large grids (e.g., 300×300 → 90k depth) → stack overflow.
3. Boundary Neglect:
   • Accessing grid[-1][0] or grid[m][n] → index errors.
4. Data Type Confusion:
   • Comparing '1' (string) with 1 (integer).
5. Diagonal Assumption:
   • Treating diagonal cells as adjacent → overconnecting.

---

3. Approach Encyclopedia

Approach 1: Brute Force (Naïve)

Idea: For each '1', recursively mark all connected lands without optimization.
Pseudocode:

def dfs(grid, i, j):  
    if i, j invalid or grid[i][j] != '1': return  
    grid[i][j] = '0'  # Mark as visited  
    dfs(grid, i+1, j); dfs(grid, i-1, j); dfs(grid, i, j+1); dfs(grid, i, j-1)  

count = 0  
for i in range(m):  
    for j in range(n):  
        if grid[i][j] == '1':  
            count += 1  
            dfs(grid, i, j)  

Complexity:

• Time: ( O(mn) ) — Each cell visited once.
• Space: ( O(mn) ) worst-case recursion depth (e.g., all lands).

Visualization:

Initial Grid:  
  1 1 0  
  1 0 1  
  0 1 1  

Step 1: (0,0) → triggers DFS → marks (0,0),(0,1),(1,0) → count=1.  
Step 2: (1,2) → triggers DFS → marks (1,2),(2,1),(2,2) → count=2.  

---

Approach 2: BFS (Optimal)

Idea: Replace recursion with a queue to avoid stack overflow.
Pseudocode:

from collections import deque  

directions = [(1,0), (-1,0), (0,1), (0,-1)]  
for i in range(m):  
    for j in range(n):  
        if grid[i][j] == '1':  
            count += 1  
            queue = deque([(i, j)])  
            grid[i][j] = '0'  
            while queue:  
                x, y = queue.popleft()  
                for dx, dy in directions:  
                    nx, ny = x+dx, y+dy  
                    if 0≤nx<m and 0≤ny<n and grid[nx][ny]=='1':  
                        grid[nx][ny] = '0'  
                        queue.append((nx, ny))  

Complexity Proof:

• Time: ( O(mn) ) — Each cell processed once.
• Space:
  • Queue: Worst-case ( O(\min(m, n)) ) (e.g., diagonal expansion).
  • Grid Modification: ( O(1) ) extra space.
• Derivation:
  • Let ( d = \min(m, n) ). The BFS queue holds ( \leq 4d ) nodes (e.g., diamond-shaped expansion).

Visualization:

Grid:  
  1 1 0  
  0 1 1  
BFS at (0,0):  
  Queue: [(0,0)] → mark (0,0) → neighbors: (0,1) valid, (1,0) invalid.  
  Queue: [(0,1)] → mark (0,1) → neighbors: (0,2) invalid, (1,1) valid.  
  Queue: [(1,1)] → mark (1,1) → neighbors: (1,2) valid.  
  Queue: [(1,2)] → mark (1,2) → neighbors: none.  
Islands = 1.  

---

Approach 3: Union-Find (DSU)

Idea: Treat each land as a node; union adjacent lands.
Pseudocode:

parent = list(range(m*n))  
rank = [0]*(m*n)  

def find(x):  
    while parent[x] != x:  
        parent[x] = parent[parent[x]]; x = parent[x]  
    return x  

def union(x, y):  
    rx, ry = find(x), find(y)  
    if rx == ry: return  
    if rank[rx] < rank[ry]: parent[rx] = ry  
    elif rank[rx] > rank[ry]: parent[ry] = rx  
    else: parent[ry] = rx; rank[rx] += 1  

count = sum(1 for i in range(m) for j in range(n) if grid[i][j]=='1')  
for i in range(m):  
    for j in range(n):  
        if grid[i][j]=='1':  
            idx = i*n + j  
            if j+1 < n and grid[i][j+1]=='1':  # Right  
                union(idx, i*n + j+1); count -= 1  
            if i+1 < m and grid[i+1][j]=='1':  # Down  
                union(idx, (i+1)*n + j); count -= 1  

Complexity:

• Time: ( O(mn \cdot \alpha(mn)) ) ≈ ( O(mn) ) (near-linear with path compression).
• Space: ( O(mn) ) for parent/rank arrays.

---

4. Code Deep Dive

Optimal Solution (BFS):

from collections import deque  

class Solution:  
    def numIslands(self, grid: List[List[str]]) -> int:  
        if not grid: return 0  
        m, n = len(grid), len(grid[0])  
        count = 0  
        directions = [(1,0), (-1,0), (0,1), (0,-1)]  
        for i in range(m):  
            for j in range(n):  
                if grid[i][j] == '1':  # Unvisited land  
                    count += 1  
                    queue = deque([(i, j)])  
                    grid[i][j] = '0'  # Mark as water  
                    while queue:  
                        x, y = queue.popleft()  
                        for dx, dy in directions:  # Check neighbors  
                            nx, ny = x + dx, y + dy  
                            if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == '1':  
                                grid[nx][ny] = '0'  # Mark neighbor  
                                queue.append((nx, ny))  
        return count  

Line-by-Line Annotations:

• Lines 1-2: Import deque; handle empty grid.
• Line 4: Initialize island counter.
• Line 5: Directions for 4-way adjacency.
• Lines 6-7: Scan all cells.
• Line 8: On finding land ('1'), increment count.
• Line 9: Initialize queue with current land.
• Line 10: Mark current cell as visited (set to '0').
• Lines 11-15: BFS: For each neighbor, if valid and unvisited, mark and enqueue.

Edge Case Handling:

• Example 1 (All Connected):
  • BFS starting at (0,0) marks all lands → count=1.
• Example 2 (Disconnected):
  • Three BFS calls for top-left, center, and bottom-right clusters → count=3.
• Single Cell:
  • grid = [['1']] → BFS marks it → count=1.

---

5. Complexity War Room

Hardware-Aware Analysis:

• Queue Memory:
  • Worst-case queue size = ( 4 \times \min(m, n) = 4 \times 300 = 1200 ) elements.
  • Each element: two integers (8 bytes) → ( 1200 \times 8 = 9.6 \text{ KB} ).
  • Fits in CPU L1/L2 cache (typically 32–512 KB).
• Grid Memory:
  • ( 300 \times 300 \times 1 \text{ byte} \approx 90 \text{ KB} ) → Fits in L3 cache (MBs).

Industry Comparison:

Approach	Time	Space	Readability	Interview Viability
Brute Force	( O(mn) )	( O(mn) )	9/10	❌ Stack overflow
BFS (Optimal)	( O(mn) )	( O(\min(m, n)) )	8/10	✅
Union-Find	( O(mn \cdot \alpha) )	( O(mn) )	6/10	⚠️ Overkill

---

6. Pro Mode Extras

Variants:

1. Diagonal Connections:
   • Change directions to include (1,1), (1,-1), (-1,1), (-1,-1).
2. Preserve Grid:
   • Use a visited matrix → space ( O(mn) ).
3. Multiple Transactions (LC 123):
   • Extend to track state (e.g., buys/sells) with dynamic programming.

Interview Cheat Sheet:

• First Mention: Time/space complexity.
• Clarify: Diagonal connections? Grid modification allowed?
• Optimize: Avoid recursion for large grids (BFS > DFS).
• Test: All '0's, all '1's, single row/column.