Number of Islands DSA Solution - Study Chapter | QuizMaker

Course

DSA Course: Interview Patterns and Problem Solving

Topic

Module 7: Graphs

Learning Outcome

After this lesson, you should be able to convert a grid into graph thinking and use DFS to mark one island at a time.

Problem Statement

Given a grid of land cells 1 and water cells 0, count how many groups of horizontally or vertically connected land exist.

Brute Force Approach

Compare every land cell with every other land cell to discover groups. This ignores locality and becomes unnecessarily slow.

Optimized Approach

Scan the grid once. When land is found, increment the count and DFS through its four-direction neighbors to mark that island.

Exact Pseudocode

count = 0
for each cell in grid:
  if cell is land:
    count += 1
    dfs(cell)
return count

dfs(row, col):
  if row or col is out of bounds:
    return
  if cell is water:
    return
  mark cell as water
  dfs four neighbors

Reference Code

class Solution:
    def numIslands(self, grid):
        if not grid:
            return 0

        rows, cols = len(grid), len(grid[0])

        def dfs(r, c):
            if r < 0 or c < 0 or r == rows or c == cols or grid[r][c] != "1":
                return
            grid[r][c] = "0"
            dfs(r + 1, c)
            dfs(r - 1, c)
            dfs(r, c + 1)
            dfs(r, c - 1)

        islands = 0
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == "1":
                    islands += 1
                    dfs(r, c)
        return islands

class Solution {
public:
    int rows, cols;

    void dfs(vector<vector<char>>& grid, int r, int c) {
        if (r < 0 || c < 0 || r == rows || c == cols || grid[r][c] != '1') return;
        grid[r][c] = '0';
        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;
        rows = grid.size();
        cols = grid[0].size();
        int islands = 0;
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] == '1') {
                    islands++;
                    dfs(grid, r, c);
                }
            }
        }
        return islands;
    }
};

class Solution {
    private int rows;
    private int cols;

    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) return 0;
        rows = grid.length;
        cols = grid[0].length;
        int islands = 0;
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] == '1') {
                    islands++;
                    dfs(grid, r, c);
                }
            }
        }
        return islands;
    }

    private void dfs(char[][] grid, int r, int c) {
        if (r < 0 || c < 0 || r == rows || c == cols || grid[r][c] != '1') return;
        grid[r][c] = '0';
        dfs(grid, r + 1, c);
        dfs(grid, r - 1, c);
        dfs(grid, r, c + 1);
        dfs(grid, r, c - 1);
    }
}

Sample Dry Run

Complexity

Edge Cases

• Diagonal land is not connected unless the prompt says so.
• An all-water grid returns 0.
• A single large island can create deep recursion.

Interview Checklist

• Use four directions only.
• Mark visited before exploring neighbors.
• Do not count the same island twice.

FAQs

It is an in-place visited marker that prevents revisiting the same island.

Yes. DFS and BFS both work as long as each land cell is marked once.

Grid DFS flood traversal.

Tags

• dsa
• graphs
• grid dfs