0200. Number of islands

0200. Number of islands#

Problem#

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.

Examples#

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

Analysis#

  • DFS:

Solution#

"""A solution using DFS"""
def solution(grid):

        R, C = len(grid), len(grid[0])
        seen = []
        
        def dfs(grid, sr, sc):
            
            if grid[sr][sc]=="1" and (sr, sc) not in seen:
                seen.append((sr, sc))
  
                # move pointer
                if sr > 0:
                    dfs(grid, sr - 1, sc)
                if sr < R - 1:
                    dfs(grid, sr + 1, sc)
                if sc > 0:
                    dfs(grid, sr, sc - 1)
                if sc < C - 1:
                    dfs(grid, sr, sc + 1)
        
        num_island = 0
        for r in range(R):
            for c in range(C):
                if grid[r][c]=="1" and (r,c) not in seen:
                    dfs(grid, r, c)
                    num_island += 1
        
        return num_island

# tests
grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
print(solution(grid))

grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
print(solution(grid))

1
3

The above implementation has an extra O(m*n) complexity, which fails to pass in the leetcode test. The reason is an extra list is introduced to store the seen land cell. If modifying the original array is allowed, we can avoid creating an extra space for storing seen elements by modifying its values in-place. The improved implementation is shown as next.

"""A solution using DFS to avoid extra O(n) space using seen"""
def solution(grid):

        R, C = len(grid), len(grid[0])
        seen = "2"
        def dfs(grid, sr, sc):
            
            if grid[sr][sc]=="1":
                grid[sr][sc] = seen
  
                # move pointer
                if sr > 0:
                    dfs(grid, sr - 1, sc)
                if sr < R - 1:
                    dfs(grid, sr + 1, sc)
                if sc > 0:
                    dfs(grid, sr, sc - 1)
                if sc < C - 1:
                    dfs(grid, sr, sc + 1)
        
        num_island = 0
        for r in range(R):
            for c in range(C):
                if grid[r][c]=="1":
                    dfs(grid, r, c)
                    num_island += 1
        
        return num_island

# tests
grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
print(solution(grid))

grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
print(solution(grid))

1
3
Contents