Neetcode - Number of Islands

Think twice, code once.

We’ve been working on Dynamic Programming problems for several days. Now, it’s time to dive into another fundamental topic in computer science: Graphs. The problem we’re tackling today is a classic in graph theory, as it highlights one of the core concepts—independency. This concept frequently appears in academic papers and statistical analysis, especially when modeling relationships between individuals or entities.

Naturally, the most straightforward approach to this problem is our old friend—the recursive solution. Let’s take a look at the code.

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int islands = 0;

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

        return islands;
    }

    void dfs(int r, int c, vector<vector<char>>& grid) {
        if (
        r < 0 || 
        c < 0 || 
        r >= grid.size() 
        || c >= grid[0].size() 
        || grid[r][c] == '0') return;

        grid[r][c] = '0';
        dfs(r + 1, c, grid);
        dfs(r - 1, c, grid);
        dfs(r, c + 1, grid);
        dfs(r, c - 1, grid);
    }
};

I was initially stuck because I didn’t know how to determine when to stop the search—specifically, when there were no more land cells connected to the starting point. Eventually, I received a helpful hint: modify the value of the current position to mark it as visited. By doing this, we can decide whether to continue exploring or terminate the search at that point.

Additionally, to ensure all islands are accounted for, we need to iterate through every row and column, checking for any land cells that haven't been visited yet. These represent disconnected islands that need to be explored separately.

It’s also worth noting that this problem can be solved using Breadth-First Search (BFS) in addition to Depth-First Search (DFS), depending on the traversal strategy you prefer.

class Solution {
  int directions[4][2] = {
    {1, 0}, {-1, 0}, 
    {0, 1}, {0, -1}
  };

public:
  int numIslands(vector<vector<char>> &grid) {
    int islands = 0;

    int rows = grid.size();
    int cols = grid[0].size();
    for (int r = 0; r < rows; ++r) {
      for (int c = 0; c < cols; ++c) {
        if (grid[r][c] == '1') {
          bfs(r, c, grid);
          ++islands;
        }
      }
    }

    return islands;
  }

  void bfs(int r, int c, vector<vector<char>> &grid) {
    queue<pair<int, int>> q;

    grid[r][c] = '0';

    q.push(make_pair(r, c));

    while (!q.empty()) {
      auto [row, col] = q.front();
      q.pop();

      for (int i = 0; i < 4; ++i) {
        int nr = row + directions[i][0];
        int nc = col + directions[i][1];

        if (nr >= 0 
        && nc >= 0 
        && nr < grid.size() 
        && nc < grid[0].size() 
        && grid[nr][nc] == '1') {
          q.push(make_pair(nr, nc));
          grid[nr][nc] = '0';
        }
      }
    }
  }
};

Both DFS and BFS have the same time complexity for this problem—O(m × n), where m is the number of rows and n is the number of columns in the grid. The difference lies in how they traverse the grid:

• DFS (Depth-First Search) explores one path as deep as possible before backtracking.
• BFS (Breadth-First Search) explores all neighboring nodes at the same level (depth) before going deeper.

In either approach, we track visited positions, typically by marking them directly in the grid (e.g., changing '1' to '0') to avoid revisiting the same land cell. This ensures that we only process each land cell once.

The recursive calls (in DFS) or queue operations (in BFS) are used to visit neighboring positions and explore the full extent of an island.

Conclusion

This opens the door to exploring the fascinating world of Graphs. Graphs are not only useful in solving algorithmic problems—they are also rich in mathematical structure and full of intriguing concepts. In the future, we’ll continue diving deeper into graph theory, not just for problem-solving, but to appreciate its broader applications and elegant ideas.