Number of Islands in JavaScript (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) surrounded by '0's (water). This problem is significant in various applications such as geographical mapping, image processing, and network connectivity.

Potential pitfalls include not correctly identifying connected components or missing edge cases where islands are at the boundaries of the grid.

Approach

To solve this problem, we can use Depth-First Search (DFS) or Breadth-First Search (BFS) to traverse the grid and mark visited lands. Here’s a step-by-step approach:

Naive Solution

A naive solution would involve checking each cell and performing a search for connected lands. However, this approach can be inefficient due to repeated searches.

Optimized Solution

An optimized solution involves using DFS or BFS to traverse and mark all connected lands starting from each unvisited land cell. This ensures each cell is processed only once.

DFS Approach

1. Iterate through each cell in the grid. 2. When a '1' is found, initiate a DFS to mark all connected '1's. 3. Increment the island count for each DFS initiation.

Algorithm

Here’s a detailed breakdown of the DFS algorithm:

Initialize a counter for the number of islands.
Iterate through each cell in the grid.
If a cell contains '1', initiate a DFS to mark all connected '1's as visited.
Increment the island counter for each DFS initiation.
Return the island counter.

Code Implementation

/**
 * @param {character[][]} grid
 * @return {number}
 */
var numIslands = function(grid) {
    if (!grid || grid.length === 0) return 0;

    let numIslands = 0;

    // Helper function to perform DFS
    const dfs = (grid, i, j) => {
        // Check for out of bounds or water
        if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] === '0') {
            return;
        }

        // Mark the cell as visited by setting it to '0'
        grid[i][j] = '0';

        // Perform DFS in all four directions
        dfs(grid, i + 1, j); // down
        dfs(grid, i - 1, j); // up
        dfs(grid, i, j + 1); // right
        dfs(grid, i, j - 1); // left
    };

    // Iterate through each cell in the grid
    for (let i = 0; i < grid.length; i++) {
        for (let j = 0; j < grid[0].length; j++) {
            if (grid[i][j] === '1') {
                numIslands++;
                dfs(grid, i, j);
            }
        }
    }

    return numIslands;
};

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. 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:

Empty grid: The function should return 0.
Grid with no land: The function should return 0.
Grid with all land: The function should return 1.

Testing these edge cases ensures the robustness of the solution.

Testing

To test the solution comprehensively, consider the following test cases:

Simple grid with one island.
Grid with multiple distinct islands.
Grid with no islands.
Large grid to test performance.

Using a testing framework like Jest can help automate and validate these test cases.

Thinking and Problem-Solving Tips

When approaching such problems, consider the following tips:

Break down the problem into smaller, manageable parts.
Visualize the problem with diagrams or examples.
Think about 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 mastering grid-based traversal algorithms. By practicing and exploring different approaches, you can enhance your problem-solving skills and prepare for more complex challenges.

Additional Resources

For further reading and practice, consider the following resources: