LeetCode Solution 200 - Number of Islands

Problem Statement

Given an m x n grid of 1s (land) and 0s (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 surrounded by water.

Example 1:

Input:

11110
11010
11000
00000

Output:

1

Example 2:

Input:

11000
11000
00100
00011

Output:

3

---

Optimal Approach

We use Depth First Search (DFS) or Breadth First Search (BFS) to traverse the grid and mark visited lands. The key idea is to iterate through the grid, and each time we find an unvisited land ('1'), we trigger a DFS/BFS to mark all connected lands as visited, incrementing our island count.

---

C++ Solution (DFS Approach)

class Solution {
public:
    void dfs(vector<vector<char>>& grid, int i, int j) {
        if (i < 0 || j < 0 || i >= grid.size() || j >= grid[0].size() || grid[i][j] == '0')
            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);
    }
    
    int numIslands(vector<vector<char>>& grid) {
        int count = 0;
        for (int i = 0; i < grid.size(); i++) {
            for (int j = 0; j < grid[0].size(); j++) {
                if (grid[i][j] == '1') {
                    count++;
                    dfs(grid, i, j);
                }
            }
        }
        return count;
    }
};

---

Step-by-Step Explanation

1. Iterate through the grid:

   • Check each cell; if it contains '1', it is part of an island.
   • Increase the island count.
   • Perform DFS/BFS to mark all connected land as visited.

2. Depth-First Search (DFS) Traversal:

   • If the cell is out of bounds or water ('0'), return.
   • Otherwise, mark the current land ('1') as visited ('0').
   • Recursively call DFS in all four directions (up, down, left, right).

3. Continue until all lands are visited:

   • Each time a new '1' is found, a new island is counted.
   • At the end, return the total count.

---

Dry Run / Execution Steps

Given Input:

11000
11000
00100
00011

Step-by-Step Execution:

1. Start at (0,0): Island found → Mark all connected lands (dfs execution).
2. Move through (0,1), (1,0), and (1,1) → All connected lands marked.
3. Encounter (2,2): New island found → Mark visited.
4. Encounter (3,3) and (3,4): Another island found → Mark visited.
5. Final count: 3 islands.

---

Alternative Approaches & Why Not?

Approach	Time Complexity	Space Complexity	Why Not?
Brute Force (Revisiting Cells Multiple Times)	O(m*n)	O(1)	Inefficient for large grids
Union-Find (Disjoint Set Union - DSU)	O(m*n)	O(m*n)	More complex to implement
Breadth-First Search (BFS)	O(m*n)	O(min(m,n))	Works well but requires queue overhead

BFS Approach (Alternative)

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int count = 0;
        int m = grid.size(), n = grid[0].size();
        vector<pair<int, int>> directions = {{0,1}, {1,0}, {0,-1}, {-1,0}};
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1') {
                    count++;
                    queue<pair<int, int>> q;
                    q.push({i, j});
                    grid[i][j] = '0';
                    
                    while (!q.empty()) {
                        auto [r, c] = q.front(); q.pop();
                        for (auto [dr, dc] : directions) {
                            int nr = r + dr, nc = c + dc;
                            if (nr >= 0 && nc >= 0 && nr < m && nc < n && grid[nr][nc] == '1') {
                                q.push({nr, nc});
                                grid[nr][nc] = '0';
                            }
                        }
                    }
                }
            }
        }
        return count;
    }
};

---

Best Solution & Why?

Approach	Time Complexity	Space Complexity	Why Best?
DFS (Recursive)	O(m*n)	O(m*n) (Recursive Stack)	Simple & efficient for dense grids
BFS (Queue-based)	O(m*n)	O(min(m,n))	Works well but has queue overhead
Union-Find (DSU)	O(m*n)	O(m*n)	More complex, useful for dynamic grid updates

Best Approach: DFS Solution

• Reason: Easy to implement, performs well in all scenarios, and has predictable complexity.

---

Complexity Analysis

Approach	Time Complexity	Space Complexity
DFS	O(m*n)	O(m*n) (Recursive)
BFS	O(m*n)	O(min(m,n)) (Queue)
DSU	O(m*n)	O(m*n)

---

Conclusion

• The DFS-based approach provides a clean and efficient way to solve the problem.
• BFS is a good alternative but requires additional memory.
• Union-Find is optimal for dynamic scenarios.
• Alternative Practice Problems:
  • Pacific Atlantic Water Flow
  • Flood Fill
  • Surrounded Regions

This concludes the Number of Islands problem solution. 🚀 Happy Coding!