NUHMAN.com

Problem Statement

Given a 2D binary grid grid, where 1 represents land and 0 represents water, return the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically.

Function Signature:

go

func numIslands(grid [][]byte) int

Example 1:

go

grid := [][]byte{
    {'1', '1', '1', '1', '0'},
    {'1', '1', '0', '1', '0'},
    {'1', '1', '0', '0', '0'},
    {'0', '0', '0', '0', '0'},
}
fmt.Println(numIslands(grid)) // Output: 1

Example 2:

go

grid := [][]byte{
    {'1', '1', '0', '0', '0'},
    {'1', '1', '0', '0', '0'},
    {'0', '0', '1', '0', '0'},
    {'0', '0', '0', '1', '1'},
}
fmt.Println(numIslands(grid)) // Output: 3

Constraints:

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 300
• grid[i][j] is either '0' or '1'.

Approach

This problem can be solved using Depth-First Search (DFS) to explore all connected components of land in the grid.

Steps:

1. DFS Traversal:

• We iterate through every cell in the grid. When we encounter a land cell (1), we treat it as the start of a new island.
• From that cell, we perform DFS to visit all the connected land cells (1) in all four directions (up, down, left, right) and mark them as visited by converting them to water (0).
• After visiting all connected cells for that island, we increment the island count.

1. Edge Cases:

• If the grid is empty (grid == nil), return 0.
• The grid can contain multiple isolated islands, which is handled by DFS.

1. Time Complexity:

• O(m * n), where m is the number of rows and n is the number of columns in the grid. We visit each cell once during DFS.

1. Space Complexity:

• O(m * n) for the recursion stack due to DFS, which can go as deep as the number of cells in the grid in the worst case.

Go Implementation

go

package main

import "fmt"

// Directions for up, down, left, and right movement
var directions = [][2]int{
    {-1, 0}, // up
    {1, 0},  // down
    {0, -1}, // left
    {0, 1},  // right
}

// DFS to explore the island
func dfs(grid [][]byte, i, j int) {
    // Base case: check if out of bounds or water
    if i < 0 || i >= len(grid) || j < 0 || j >= len(grid[0]) || grid[i][j] == '0' {
        return
    }

    // Mark the current land as visited by setting it to '0'
    grid[i][j] = '0'

    // Explore all four directions
    for _, dir := range directions {
        dfs(grid, i+dir[0], j+dir[1])
    }
}

// Function to return the number of islands
func numIslands(grid [][]byte) int {
    if len(grid) == 0 {
        return 0
    }

    islandCount := 0

    // Iterate through each cell in the grid
    for i := 0; i < len(grid); i++ {
        for j := 0; j < len(grid[0]); j++ {
            // If we encounter a '1' (land), it's the start of a new island
            if grid[i][j] == '1' {
                // Perform DFS to visit all land connected to this cell
                dfs(grid, i, j)
                // After visiting all the connected land, increment island count
                islandCount++
            }
        }
    }

    return islandCount
}

func main() {
    // Example 1
    grid1 := [][]byte{
        {'1', '1', '1', '1', '0'},
        {'1', '1', '0', '1', '0'},
        {'1', '1', '0', '0', '0'},
        {'0', '0', '0', '0', '0'},
    }
    fmt.Println(numIslands(grid1)) // Output: 1

    // Example 2
    grid2 := [][]byte{
        {'1', '1', '0', '0', '0'},
        {'1', '1', '0', '0', '0'},
        {'0', '0', '1', '0', '0'},
        {'0', '0', '0', '1', '1'},
    }
    fmt.Println(numIslands(grid2)) // Output: 3
}

Explanation of the Code:

1. DFS Helper Function (dfs):

• Input: Takes the grid, current row i, and column j to perform a DFS.
• Base Case: If the current cell is out of bounds or is water ('0'), return.
• Marking as Visited: Convert the current land cell ('1') to water ('0') to mark it as visited.
• Recursive Calls: Explore all four directions (up, down, left, right) using the directions array.

2. numIslands Function:

• Input: Takes the 2D grid (grid) representing the map of the islands.
• Grid Iteration: Iterates through each cell in the grid.
• Island Detection: If a '1' is encountered, it means we've found an unvisited island. We then call the dfs function to visit all connected land cells and mark them as visited.
• Island Count: After completing the DFS for an island, we increment the island count.

3. Main Function:

• Creates two example grids (grid1 and grid2).
• Calls the numIslands function and prints the result for each grid.

Example Walkthrough

Example 1:

Input:

go

grid := [][]byte{
    {'1', '1', '1', '1', '0'},
    {'1', '1', '0', '1', '0'},
    {'1', '1', '0', '0', '0'},
    {'0', '0', '0', '0', '0'},
}

The grid represents the following:

11110
11010
11000
00000

1. Island 1:

• Starting from grid[0][0], we perform DFS and mark all connected land as visited.
• This entire part of the grid forms one island.

Output: 1

Example 2:

Input:

go

grid := [][]byte{
    {'1', '1', '0', '0', '0'},
    {'1', '1', '0', '0', '0'},
    {'0', '0', '1', '0', '0'},
    {'0', '0', '0', '1', '1'},
}

The grid represents the following:

11000
11000
00100
00011

1. Island 1:

• Starting from grid[0][0], we perform DFS to mark the entire connected land as visited.

1. Island 2:

• Starting from grid[2][2], we perform DFS and mark all connected land as visited.

1. Island 3:

• Starting from grid[3][3], we perform DFS and mark all connected land as visited.

Output: 3

Conclusion

The LeetCode 200: Number of Islands problem is solved efficiently using DFS to explore each island and mark the connected land. The time complexity is O(m * n), and the space complexity is O(m * n) due to the recursive DFS stack. This approach is optimal for grid traversal problems like this one.