Last updated on July 19th, 2024 at 07:37 pm

Here, We see Number of Islands LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.

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

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

1. Number of Islands LeetCode Solution 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;
    }
};

2. Number of Islands LeetCode Solution 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. Number of Islands LeetCode Solution 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;
};

4. Number of Islands LeetCode Solution 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)