Size of Islands in JavaScript with Time Complexity Analysis

Given a 2d grid map of '1's (land) and '0's (water), find the islands and return an array containing their sizes. An island is surrounded by water and is formed by connecting adjacent land cells horizontally or vertically. You may assume all four edges of the grid are 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: [9]
Explanation:  There is only one island with size 9

Example 2:

Input:
1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1

Output: [1, 4, 2]
Explanation There are three islands with sizes of 1, 4 and 2

Note: The islands' sizes can be returned in any order

Understanding the Problem

The core challenge of this problem is to identify and count the sizes of all 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 correctly identifying all connected components or miscounting the size of an island due to improper traversal.

Approach

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

Naive Solution

A naive solution would involve checking each cell and performing a search from each '1' to find all connected '1's. This approach is not optimal as it may involve redundant searches.

Optimized Solution

An optimized solution involves marking cells as visited once they are part of an island to avoid redundant searches. We can use DFS or BFS for this purpose.

Depth-First Search (DFS) Approach

1. Iterate through each cell in the grid. 2. When a '1' is found, initiate a DFS to explore the entire island. 3. Mark all visited cells as '0' to avoid revisiting. 4. Count the number of cells in the island and add the count to the result array.

Breadth-First Search (BFS) Approach

1. Similar to DFS, but use a queue to explore the island level by level. 2. This approach can be more memory efficient in some cases.

Algorithm

Here’s a step-by-step breakdown of the DFS algorithm:

Initialize an empty array to store the sizes of islands.
Iterate through each cell in the grid.
If a cell contains '1', initiate a DFS from that cell.
In the DFS function, use a stack to explore all connected '1's.
Mark each visited cell as '0' and count the number of cells in the island.
After the DFS completes, add the count to the result array.

Code Implementation

Below is the JavaScript implementation of the DFS approach:

/**
 * @param {character[][]} grid
 * @return {number[]}
 */
function numIslands(grid) {
    // Helper function to perform DFS
    function 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 0;
        }
        
        // Mark the cell as visited
        grid[i][j] = '0';
        
        // Initialize size of this island
        let size = 1;
        
        // Explore all 4 directions
        size += dfs(grid, i + 1, j);
        size += dfs(grid, i - 1, j);
        size += dfs(grid, i, j + 1);
        size += dfs(grid, i, j - 1);
        
        return size;
    }
    
    let sizes = [];
    
    // 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') {
                // Perform DFS and get the size of the island
                let size = dfs(grid, i, j);
                sizes.push(size);
            }
        }
    }
    
    return sizes;
}

// Example usage:
const grid1 = [
    ['1', '1', '1', '1', '0'],
    ['1', '1', '0', '1', '0'],
    ['1', '1', '0', '0', '0'],
    ['0', '0', '0', '0', '0']
];
console.log(numIslands(grid1)); // Output: [9]

const grid2 = [
    ['1', '1', '0', '0', '0'],
    ['1', '1', '0', '0', '0'],
    ['0', '0', '1', '0', '0'],
    ['0', '0', '0', '1', '1']
];
console.log(numIslands(grid2)); // Output: [4, 1, 2]

Complexity Analysis

The time complexity of the DFS 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.

Edge Cases

Potential edge cases include:

Empty grid: The function should return an empty array.
Grid with no land: The function should return an empty array.
Grid with all land: The function should return an array with one element equal to the total number of cells.

Testing for these edge cases ensures the robustness of the solution.

Testing

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

Simple grids with one or two islands.
Grids with varying sizes and shapes of islands.
Edge cases as mentioned above.

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

Thinking and Problem-Solving Tips

When approaching such problems, it’s essential to:

Understand the problem requirements and constraints thoroughly.
Break down the problem into smaller, manageable parts.
Consider different approaches and their trade-offs.
Write clean, modular code and test it extensively.

Practicing similar problems and studying algorithms like DFS and BFS can significantly improve problem-solving skills.

Conclusion

In this blog post, we discussed how to find the sizes of islands in a 2D grid using the DFS approach. We covered the problem definition, approach, algorithm, code implementation, complexity analysis, edge cases, and testing. Understanding and solving such problems is crucial for developing strong problem-solving skills in computer science.

Additional Resources

For further reading and practice, consider the following resources: