Number of Islands in C++ (Time Complexity: O(M*N))

Given a 2d grid map of '1's (land) and '0's (water), count 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:
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:
1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1

Output: 3

Understanding the Problem

The core challenge of this problem is to identify and count distinct islands in a 2D grid. An island is defined as a group of horizontally or vertically connected '1's (land). The problem is significant in various applications such as geographical mapping, image processing, and network connectivity.

Potential pitfalls include not properly handling the boundaries of the grid and not marking visited cells, which can lead to incorrect counts or infinite loops.

Approach

To solve this problem, we can use Depth-First Search (DFS) or Breadth-First Search (BFS) to traverse the grid. The idea is to iterate through each cell in the grid, and when a '1' is found, initiate a DFS/BFS to mark all connected '1's as visited. This ensures that each island is counted only once.

Naive Solution

A naive solution would involve checking each cell and its neighbors repeatedly, leading to redundant checks and higher time complexity. This approach is not optimal.

Optimized Solution

The optimized solution involves using DFS or BFS to mark all cells of an island as visited once an unvisited '1' is found. This reduces redundant checks and ensures each cell is processed only once.

Algorithm

Here is a step-by-step breakdown of the DFS approach:

Initialize a counter for the number of islands.
Iterate through each cell in the grid.
When a '1' is found, increment the island counter and initiate a DFS to mark all connected '1's as visited.
In the DFS function, mark the current cell as visited and recursively visit all adjacent cells that are '1'.
Continue this process until all cells are processed.

Code Implementation

#include <vector>
using namespace std;

// Function to perform DFS and mark visited cells
void dfs(vector<vector<char>>& grid, int i, int j) {
    // Check for boundary conditions and if the cell is water or already visited
    if (i < 0 || i >= grid.size() || j < 0 || j >= grid[0].size() || grid[i][j] == '0') {
        return;
    }
    
    // Mark the cell as visited by setting it to '0'
    grid[i][j] = '0';
    
    // Recursively visit all adjacent cells
    dfs(grid, i + 1, j); // Down
    dfs(grid, i - 1, j); // Up
    dfs(grid, i, j + 1); // Right
    dfs(grid, i, j - 1); // Left
}

int numIslands(vector<vector<char>>& grid) {
    if (grid.empty()) return 0;
    
    int num_islands = 0;
    
    // Iterate through each cell in the grid
    for (int i = 0; i < grid.size(); ++i) {
        for (int j = 0; j < grid[0].size(); ++j) {
            // If a '1' is found, it's a new island
            if (grid[i][j] == '1') {
                ++num_islands;
                // Perform DFS to mark all connected '1's
                dfs(grid, i, j);
            }
        }
    }
    
    return num_islands;
}

Complexity Analysis

The time complexity of this approach is O(M*N), where M is the number of rows and N is the number of columns in the grid. This is because each cell is visited once. The space complexity is O(M*N) in the worst case due to the recursion stack in DFS.

Edge Cases

Potential edge cases include:

An empty grid.
A grid with no '1's (all water).
A grid with all '1's (one large island).

Each of these cases should be tested to ensure the algorithm handles them correctly.

Testing

To test the solution comprehensively, include a variety of test cases:

Simple cases with small grids.
Grids with multiple small islands.
Grids with one large island.
Edge cases as mentioned above.

Using a testing framework like Google Test can help automate and manage these tests effectively.

Thinking and Problem-Solving Tips

When approaching such problems, consider the following tips:

Break down the problem into smaller, manageable parts.
Think about different traversal methods (DFS, BFS) and their implications.
Consider edge cases and how to handle them.
Practice similar problems to improve problem-solving skills.

Conclusion

Understanding and solving the "Number of Islands" problem is crucial for developing skills in grid traversal and graph algorithms. By practicing and exploring different approaches, one can improve their problem-solving abilities and prepare for more complex challenges.

Additional Resources

For further reading and practice, consider the following resources: