Number of islands(Do in Grid and Graph Both)

Problem Overview

The problem "Number of Islands" on LeetCode is a classic example of graph traversal using depth-first search (DFS) or breadth-first search (BFS). It involves finding the number of connected groups of "land" in a grid representation of water and land. This problem helps strengthen one’s understanding of graph data structures and traversal algorithms.

Link to the problem: Number of Islands

Understanding the Problem

You are given a 2D grid of '1's (land) and '0's (water). An island is formed by connecting adjacent lands horizontally or vertically. Your task is to count the number of islands present in the grid.

Example:

Input:
11000
11000
00100
00011

Output: 3

In the given grid, there are three separate islands.

Key DSA Concepts and Theory

Graph Representation

In this problem, the 2D grid acts as a graph where each cell is a node. A '1' is a node part of a landmass (an island), and a '0' represents water, which is not part of an island.

Graph Traversal

Graph traversal algorithms like Depth-First Search (DFS) and Breadth-First Search (BFS) are essential for navigating through the graph encoded within the grid:

• Depth-First Search (DFS): This algorithm explores as far as possible along each branch before backtracking. In our case, DFS will help in marking connected components of '1's as visited.

• Breadth-First Search (BFS): This algorithm explores all the neighbor nodes at the present depth before moving on to nodes at the next depth level.

Component Counting

Counting connected components in a graph is a common problem. An "island" represents a connected component in the grid graph.

Solution Approach

We can solve the problem using either DFS or BFS. Here, we'll discuss both approaches.

Depth-First Search (DFS) Approach

The idea is to start from a '1' (land), initiate a DFS to mark the entire island as visited by converting connected '1's to '0's, and then increase the island count.

Algorithm:

1. Initialize a count to zero to track the number of islands.
2. Iterate through each cell in the grid.
3. If the cell contains '1', it signifies an unvisited land; increment the island count and perform a DFS from this cell.
4. During DFS, mark all connected '1's as '0' to avoid recounting them.
5. Continue this process for the entire grid.
6. Return the island count.

C++ Code:

class Solution {
public:
    void dfs(vector<vector<char>>& grid, int r, int c) {
        int nr = grid.size();
        int nc = grid[0].size();

        if (r < 0 || c < 0 || r >= nr || c >= nc || grid[r][c] == '0') {
            return;
        }

        grid[r][c] = '0'; // Mark as visited

        // Call DFS on all neighboring cells (up, down, left, right)
        dfs(grid, r - 1, c);
        dfs(grid, r + 1, c);
        dfs(grid, r, c - 1);
        dfs(grid, r, c + 1);
    }

    int numIslands(vector<vector<char>>& grid) {
        if (grid.empty()) return 0;

        int num_islands = 0;
        for (int r = 0; r < grid.size(); ++r) {
            for (int c = 0; c < grid[0].size(); ++c) {
                if (grid[r][c] == '1') {
                    ++num_islands;
                    dfs(grid, r, c);
                }
            }
        }

        return num_islands;
    }
};

Java Code:

class Solution {
    void dfs(char[][] grid, int r, int c) {
        int nr = grid.length;
        int nc = grid[0].length;

        if (r < 0 || c < 0 || r >= nr || c >= nc || grid[r][c] == '0') {
            return;
        }

        grid[r][c] = '0'; // Mark as visited

        dfs(grid, r - 1, c);
        dfs(grid, r + 1, c);
        dfs(grid, r, c - 1);
        dfs(grid, r, c + 1);
    }

    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }

        int num_islands = 0;
        for (int r = 0; r < grid.length; ++r) {
            for (int c = 0; c < grid[0].length; ++c) {
                if (grid[r][c] == '1') {
                    ++num_islands;
                    dfs(grid, r, c);
                }
            }
        }

        return num_islands;
    }
}

Breadth-First Search (BFS) Approach

Algorithm:

1. Initialize a count for islands.
2. Iterate through each cell in the grid.
3. For each '1', increment the island count and start a BFS to set all connected lands to '0'.
4. Use a queue to manage BFS traversal.
5. Return the island count at the end.

This BFS approach is not directly covered in the examples above but is similar to DFS with a queue used to process the breadth-first traversal.

Time and Space Complexity Analysis

• Time Complexity: Both DFS and BFS approaches require O(N * M) time, where N is the number of rows and M is the number of columns in the grid, since we potentially visit each cell once.

• Space Complexity:

  • For DFS, the space complexity is O(N * M) in the worst case due to recursion stack space.
  • For BFS, the space complexity is O(min(N, M)) since the queue could contain all elements of a row/column in the worst case.

Common Mistakes to Avoid

• Boundary Conditions: Ensure that when you're doing DFS or BFS, you check the boundaries of the grid to avoid index out of range errors.
• Proper Visitation Marking: Forgetting to mark the node as visited can lead to infinite loops. Make sure to mark cells correctly as visited ('0') once they're part of an island count.
• Grid Validity: Always check if the grid is non-empty at the beginning of the function to avoid erroneous operations on a null or empty grid.

Similar Problems on Leetcode

• 200. Number of Connected Components in an Undirected Graph
• 733. Flood Fill
• 1254. Number of Closed Islands

Additional Resources and References

• For a detailed understanding of graph traversal methods, consider reading foundational texts on graph theory.
• Visualizations of DFS and BFS can provide a clearer insight into how the algorithms progress through a grid or graph.
• Books like "Introduction to Algorithms" by Cormen et al., offer a comprehensive analysis of graph algorithms, which can be beneficial.