Medium

Number of Islands

026

Given a 0/1 grid, return the number of connected groups of 1s using four-directional adjacency.

EXAMPLES

Example 1

Input
{
  "grid": [
    [
      1,
      1,
      0
    ],
    [
      0,
      1,
      0
    ],
    [
      1,
      0,
      1
    ]
  ]
}

Output
3

FUNCTION SHAPE

grid: intMatrix→int

SOLUTION NOTE

BFS will TLE, (prefer dfs solution in this case) but this works. As you can see we leverage the bfs template: instead of maintaining a visited set we can simply set the grid[i][j] as -1, and instead of adjlist for neighbours for grid graph problems we can simply use a directions array. (what would a diagonals dirs look like, or one that could move in the direction of knights on a chess board?) It is also common to have an isInBounds() function.

We still need to iterate over the grid, and run BFS for all 1's. Note that we will only run bfs once for each island, because for each island we will visit all neighbouring 1's in that island, and set them to -1. We skip 0's as well.

Reveal reference solution +

pythonREFERENCE

# BFS Solution
def numIslands(self, grid: List[List[str]]) -> int:
    dirs = [(0,1),(0,-1),(1,0),(-1,0)]
    m,n = len(grid), len(grid[0])
    def isInBounds(i,j):
        return 0 <= i < m and 0 <= j < n

    def bfs(i,j):
        q = deque([(i,j)])
        while q:
            for _ in range(len(q)):
                i,j = q.popleft()
                grid[i][j] = -1
                for x,y in dirs:
                    ii,jj = i+x,j+y
                    if isInBounds(ii,jj) and grid[ii][jj] == '1':
                        q.append((ii,jj))

    res = 0
    for i in range(m):
        for j in range(n):
            if grid[i][j] == '1':
                res += 1
                bfs(i, j)

    return res

# DFS Solution
def numIslands(self, grid: List[List[str]]) -> int:
    dirs = [(0,1),(0,-1),(1,0),(-1,0)]
    m,n = len(grid), len(grid[0])
    def isInBounds(i,j):
        return 0 <= i < m and 0 <= j < n
    def dfs(i, j):
        if not isInBounds(i,j) or grid[i][j] != '1':
            return
        grid[i][j] = -1 # mark visited
        for x,y in dirs:
            dfs(i + x, j + y)
    res = 0
    for i in range(m):
        for j in range(n):
            if grid[i][j] == '1':
                res += 1
                dfs(i, j)

    return res

TimeO(m*n)

SpaceO(m*n)

Open on LeetCode ↗