Skip to main content

Number of Islands

Question​

Given an m x n binary grid representing 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, but not diagonally.

Assume that all four edges of the grid are all surrounded by water.

Example
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

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 = len(grid)

n = len(grid[i])

1 <= m, n <= 300

grid[i][j] is 0 or 1.

TC

O(m*n)

SC

O(m*n)

Solution​

matrix/Number of Islands.py
def solution(grid):
    def find_island(i, j):
        if len(grid[0]) > i and i >= 0 and len(grid) > j and j >= 0 and grid[i][j] == 1:
            grid[i][j] = 0
            find_island(i, j - 1)
            find_island(i, j + 1)
            find_island(i - 1, j)
            find_island(i + 1, j)
        else:
            return

    num_island = 0
    for i in range(0, len(grid)):
        for j in range(0, len(grid[0])):
            if grid[i][j] == 1:
                num_island += 1
                find_island(i, j)
                #print(grid)

    return num_island


grid = [
    [1, 1, 0, 0, 0],
    [0, 1, 0, 0, 1],
    [1, 0, 0, 1, 1],
    [0, 0, 0, 0, 0],
    [1, 0, 1, 0, 1]
]

result = solution(grid)
#print(result)
Stepgrid
1[0, 0, 0, 0, 0]
[0, 0, 0, 0, 1]
[1, 0, 0, 1, 1]
[0, 0, 0, 0, 0]
[1, 0, 1, 0, 1]
2[0, 0, 0, 0, 0]
[0, 0, 0, 0, 0]
[1, 0, 0, 0, 0]
[0, 0, 0, 0, 0]
[1, 0, 1, 0, 1]
3[0, 0, 0, 0, 0]
[0, 0, 0, 0, 0]
[0, 0, 0, 0, 0]
[0, 0, 0, 0, 0]
[1, 0, 1, 0, 1]
4[0, 0, 0, 0, 0]
[0, 0, 0, 0, 0]
[0, 0, 0, 0, 0]
[0, 0, 0, 0, 0]
[0, 0, 1, 0, 1]
5[0, 0, 0, 0, 0]
[0, 0, 0, 0, 0]
[0, 0, 0, 0, 0]
[0, 0, 0, 0, 0]
[0, 0, 0, 0, 1]
6[0, 0, 0, 0, 0]
[0, 0, 0, 0, 0]
[0, 0, 0, 0, 0]
[0, 0, 0, 0, 0]
[0, 0, 0, 0, 0]
result
6