LeetCode 200. Number of Islands

Description

https://leetcode.com/problems/number-of-islands/

Given an m x n 2d grid 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

Constraints:

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

Explanation

We can use Depth First Search to solve the problem. If the grid cell is ‘1’, an island is found, we mark it to ‘0’ and continue to find all the remaining adjacent ‘1’ which belongs to the same island.

Python Solution

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        count = 0
        
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] != '0':  
                    self.helper(grid, i, j)
                    count += 1

        return count
    
    def helper(self, grid, i, j):
        if i < 0 or i > len(grid) - 1 or j < 0 or j > len(grid[0]) - 1:
            return
        
        if grid[i][j] == '0':
            return

        grid[i][j] = '0'
        
        self.helper(grid, i - 1, j)
        self.helper(grid, i + 1, j)
        self.helper(grid, i, j - 1)
        self.helper(grid, i, j + 1)        
  • Time complexity: O(M * N), where M is the number of rows and N is the number of columns.
  • Space complexity: O(M * N).

3 Thoughts to “LeetCode 200. Number of Islands”

  1. class Solution {
    public int numIslands(char[][] grid) {
    if(grid == null || grid.length ==0 || grid[0].length ==0) return 0;
    int count =0;
    int m = grid.length;
    int n = grid[0].length;

    for(int i=0; i<m; i++){
    for(int j=0; j<n;j++){
    if(grid[i][j] == '1'){
    count++;
    merge(grid,i,j);
    }
    }
    }

    return count;
    }

    private void merge(char[][] grid,int i,int j){
    int m = grid.length;
    int n = grid[0].length;
    if(i=m || j=n || grid[i][j]!=’1′) return;

    grid[i][j]=’X’;
    merge(grid,i-1,j);
    merge(grid,i+1,j);
    merge(grid,i,j-1);
    merge(grid,i,j+1);

    }
    }

Leave a Reply

Your email address will not be published.