Last updated on January 7th, 2025 at 03:14 am

Here, we see the Number of Islands LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Breadth-First-Search, Depth-First-Search, Union-Find

Companies

Amazon, Facebook, Google, Microsoft, Zenefits

Level of Question

Medium

Number of Islands LeetCode Solution

1. 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

2. Coding Pattern Used in Solution

The coding pattern used in all the provided implementations is “Islands”. This pattern is commonly used to solve problems where you need to traverse a grid to identify and count distinct connected components (e.g., islands in a 2D grid). The traversal is typically done using Depth-First Search (DFS) or Breadth-First Search (BFS).

3. Code Implementation in Different Languages

3.1 Number of Islands C++

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int m = grid.size(), n = m ? grid[0].size() : 0, islands = 0, offsets[] = {0, 1, 0, -1, 0};
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1') {
                    islands++;
                    grid[i][j] = '0';
                    queue<pair<int, int>> todo;
                    todo.push({i, j});
                    while (!todo.empty()) {
                        pair<int, int> p = todo.front();
                        todo.pop();
                        for (int k = 0; k < 4; k++) {
                            int r = p.first + offsets[k], c = p.second + offsets[k + 1];
                            if (r >= 0 && r < m && c >= 0 && c < n && grid[r][c] == '1') {
                                grid[r][c] = '0';
                                todo.push({r, c});
                            }
                        }
                    }
                }
            }
        }
        return islands;
    }
};

3.2 Number of Islands Java

public class Solution {
    private int n;
    private int m;
    public int numIslands(char[][] grid) {
        int count = 0;
        n = grid.length;
        if (n == 0) return 0;
        m = grid[0].length;
        for (int i = 0; i < n; i++){
            for (int j = 0; j < m; j++)
                if (grid[i][j] == '1') {
                    DFSMarking(grid, i, j);
                    ++count;
                }
        }    
        return count;
    }

    private void DFSMarking(char[][] grid, int i, int j) {
        if (i < 0 || j < 0 || i >= n || j >= m || grid[i][j] != '1') return;
        grid[i][j] = '0';
        DFSMarking(grid, i + 1, j);
        DFSMarking(grid, i - 1, j);
        DFSMarking(grid, i, j + 1);
        DFSMarking(grid, i, j - 1);
    }
}

3.3 Number of Islands JavaScript

var numIslands = function(grid) {
    let count = 0;
    function depthSearch(x, y) {
        if (grid[x][y] === '1') {
            grid[x][y] = '0';
        } else {
            return;
        }
        if (x < grid.length - 1) {
            depthSearch(x+1, y);
        }
        if (y < grid[x].length - 1) {
            depthSearch(x, y+1);
        }
        if (x > 0 && x < grid.length) {
            depthSearch(x-1, y);
        }
        if (y > 0 && y < grid[x].length) {
            depthSearch(x, y-1);
        }
    }
    for (let i = 0; i < grid.length; i++) {
        for (let j = 0; j < grid[i].length; j++) {
            if (grid[i][j] === '1') {
                count++;
                depthSearch(i, j);
            }
        }
    }
    return count;
};

3.4 Number of Islands Python

class Solution(object):
    def numIslands(self, grid):
        if not grid:
            return 0
        count = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == '1':
                    self.dfs(grid, i, j)
                    count += 1
        return count
    def dfs(self, grid, i, j):
        if i<0 or j<0 or i>=len(grid) or j>=len(grid[0]) or grid[i][j] != '1':
            return
        grid[i][j] = '#'
        self.dfs(grid, i+1, j)
        self.dfs(grid, i-1, j)
        self.dfs(grid, i, j+1)
        self.dfs(grid, i, j-1)

4. Time and Space Complexity

	Time Complexity	Space Complexity
C++	O(M * N)	O(min(M, N))
Java	O(M * N)	O(M * N)
JavaScript	O(M * N)	O(M * N)
Python	O(M * N)	O(M * N)

Here:
M is the number of rows in the grid.
N is the number of columns in the grid.