LeetCode Solution 200 - Number of Islands

Problem Statement:

Given an m x n grid consisting 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 surrounded by water.

Example:

Input:

grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]

Output: 3

---

Optimal Approach: DFS (Depth First Search)

Approach Explanation:

• Use DFS to explore and mark all connected land cells.
• Iterate through the grid and count the number of DFS calls (each indicating a new island).
• Modify the grid in place to avoid extra space usage.

C++ Solution:

class Solution {
public:
    void dfs(vector<vector<char>>& grid, int r, int c) {
        int m = grid.size(), n = grid[0].size();
        if (r < 0 || c < 0 || r >= m || c >= n || grid[r][c] == '0') return;
        grid[r][c] = '0'; // Mark as visited
        vector<int> dir = {-1, 0, 1, 0, -1};
        for (int i = 0; i < 4; ++i) {
            dfs(grid, r + dir[i], c + dir[i + 1]);
        }
    }
    
    int numIslands(vector<vector<char>>& grid) {
        if (grid.empty()) return 0;
        int m = grid.size(), n = grid[0].size(), count = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == '1') {
                    ++count;
                    dfs(grid, i, j);
                }
            }
        }
        return count;
    }
};

---

Step-by-Step Execution:

1. Initialization: Iterate over each cell in the grid.
2. DFS Traversal: If a '1' (land) is found, perform DFS to mark all connected lands as visited.
3. Counting Islands: Increase the count for each DFS call initiated from an unvisited '1'.
4. Return the Count: The total number of DFS calls represents the number of islands.

---

Alternative Approaches & Why Not?

Approach	Time Complexity	Space Complexity	Drawback
Brute Force	O(m * n * (m + n))	O(m * n)	Inefficient for large grids
BFS (Iterative)	O(m * n)	O(m * n)	Similar complexity, but queue overhead
Union-Find (Disjoint Set)	O(m * n)	O(m * n)	Complex implementation

Why DFS is the Best?

• DFS is efficient with O(m * n) complexity.
• In-place modification avoids extra space usage.
• Simple and easy-to-implement approach.

---

Complexity Analysis:

• Time Complexity: O(m * n), as each cell is visited once.
• Space Complexity: O(m * n) for recursive stack space (in worst-case scenarios).

---

Conclusion:

• Best Approach: DFS with in-place modification.
• Key Idea: Start DFS from each unvisited '1' and mark all connected lands.
• Efficiency: O(m * n) time complexity.
• Alternative Practice Problems:
  • Pacific Atlantic Water Flow
  • Flood Fill
  • Surrounded Regions

This solution efficiently finds the number of islands using DFS, making it optimal for large grids.