Solving LeetCode's Number of Islands: A Deep Dive into DFS

Introduction

The Number of Islands problem is a classic example of depth-first search (DFS) application in grid traversal. In this article, I'll walk you through my thought process and implementation strategy.

Let me explain my approach to the Number of Islands problem.

Problem Understanding

This problem can be categorized as a grid traversal pattern where we need to:

1. Count the number of distinct islands


2. Define an island as a group of connected '1's


3. Handle the grid modification efficiently

Approach

I'll use DFS (Depth-First Search) for this problem because:

1. It's a natural fit for exploring connected components


2. We can modify the input grid to track visited cells


3. It provides a clean recursive solution

Implementation Strategy

Let me break down the key components:

1. Main Function:

• Iterate through each cell in the grid


• When we find a '1', increment our island counter


• Start DFS exploration from that cell

1. DFS Helper Function:
   
   
   
   
   • Check boundary conditions
   
   
   • Verify if current cell is part of an island
   
   
   • Mark visited cells
   
   
   • Explore in all four directions
   
   
   
   

Edge Cases

• Empty grid


• Single row/column grid


• Grid with no islands


• Grid with all islands

Complexity Analysis

• Time: O(M × N) where M is rows and N is columns


• Space: O(M × N) worst case for the recursion stack

Key Optimization

Instead of using a separate visited set, we modify the input grid directly by marking visited cells with a different value. This approach:

1. Saves space


2. Simplifies our logic


3. Maintains the connected component property

My Implementation

/**

 * @param {character[][]} grid

 * @return {number}

 */

var numIslands = function (grid) {

  // We start with a counter and grid size

  var count = 0;

  const y = grid.length;

  const x = grid[0].length;

  // Handles the recursive exploration

  function dfs(i, j) {

    if (i < 0 || i >= y || j < 0 || j >= x || grid[i][j] !== "1") return;

    // Mark the cell as visited

    grid[i][j] = "0";

    dfs(i - 1, j);

    dfs(i, j + 1);

    dfs(i + 1, j);

    dfs(i, j - 1);

  }

  // Main loop to iterate through the grid

  for (let i = 0; i < grid.length; i++) {

    for (let j = 0; j < grid[i].length; j++) {

      if (grid[i][j] === "1") {

        count++;

        dfs(i, j);

      }

    }

  }

  return count;

};



const grid = [

  ["1", "1", "0", "0", "0"],

  ["1", "1", "0", "0", "0"],

  ["0", "0", "1", "0", "0"],

  ["0", "0", "0", "1", "1"],

];



console.log(numIslands(grid));