Number of Islands - LeetCode Daily Challenge

Problem Statement

Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.

An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1

Input: grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
Output: 1

Example 2

Input: grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
Output: 3

Prerequisite

Video Explanation

Java Code

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

    private void dfs(int row, int col, char[][] grid) {
        if(row < 0 || row >= grid.length || col < 0 || col >= grid[0].length || grid[row][col] != '1') {
            return;
        }
        grid[row][col] = '2';
        for(int[] direction : directions) {
            int new_row = row + direction[0];
            int new_col = col + direction[1];
            dfs(new_row, new_col, grid);
        }
    }

    public int numIslands(char[][] grid) {
        int count = 0;
        for(int i = 0; i < grid.length; i++) {
            for(int j = 0; j < grid[0].length; j++) {
                if(grid[i][j] == '1') {
                    dfs(i, j, grid);
                    count += 1;
                }
            }
        }
        return count;
    }
}

C++ Code

class Solution {
public:
    vector<vector<int>> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    
    void dfs(int row, int col, vector<vector<char>>& grid) {
        if (row < 0 || row >= grid.size() || col < 0 || col >= grid[0].size() || grid[row][col] != '1') {
            return;
        }
        grid[row][col] = '2';
        for (vector<int>& direction : directions) {
            int new_row = row + direction[0];
            int new_col = col + direction[1];
            dfs(new_row, new_col, grid);
        }
    }

    int numIslands(vector<vector<char>>& grid) {
        int count = 0;
        for (int i = 0; i < grid.size(); i++) {
            for (int j = 0; j < grid[0].size(); j++) {
                if (grid[i][j] == '1') {
                    dfs(i, j, grid);
                    count += 1;
                }
            }
        }
        return count;
    }
};

Python Code

class Solution:
    directions = [[-1, 0], [1, 0], [0, -1], [0, 1]]

    def dfs(self, row, col, grid):
        if row < 0 or row >= len(grid) or col < 0 or col >= len(grid[0]) or grid[row][col] != '1':
            return
        grid[row][col] = '2'
        for direction in self.directions:
            new_row, new_col = row + direction[0], col + direction[1]
            self.dfs(new_row, new_col, grid)

    def numIslands(self, grid):
        count = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == '1':
                    self.dfs(i, j, grid)
                    count += 1
        return count

Javascript Code

var numIslands = function(grid) {
    const directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];

    function dfs(row, col) {
        if (row < 0 || row >= grid.length || col < 0 || col >= grid[0].length || grid[row][col] !== '1') {
            return;
        }
        grid[row][col] = '2';
        for (const direction of directions) {
            const new_row = row + direction[0];
            const new_col = col + direction[1];
            dfs(new_row, new_col);
        }
    }

    let count = 0;
    for (let i = 0; i < grid.length; i++) {
        for (let j = 0; j < grid[0].length; j++) {
            if (grid[i][j] === '1') {
                dfs(i, j);
                count += 1;
            }
        }
    }
    return count;
};

Go Code

package main

func numIslands(grid [][]byte) int {
    directions := [][]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}

    var dfs func(row, col int)
    dfs = func(row, col int) {
        if row < 0 || row >= len(grid) || col < 0 || col >= len(grid[0]) || grid[row][col] != '1' {
            return
        }
        grid[row][col] = '2'
        for _, direction := range directions {
            new_row, new_col := row+direction[0], col+direction[1]
            dfs(new_row, new_col)
        }
    }

    count := 0
    for i := 0; i < len(grid); i++ {
        for j := 0; j < len(grid[0]); j++ {
            if grid[i][j] == '1' {
                dfs(i, j)
                count += 1
            }
        }
    }
    return count
}

Complexity Analysis

Time Complexity: O(m * n), where m is the number of rows and n is the number of columns in the grid.
Space Complexity: O(m * n), where m is the number of rows and n is the number of columns in the grid.