Skip to content

200. Number of Islands

Medium

Description

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

Constraints:

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

Solutions πŸ”’

Approach: BFS on Grid/Maze/2D Matrix

Time complexity: \(O(mn)\), where \(m\) is the number of rows and \(n\) is the number of columns in the grid.

Space complexity: \(O(min(m,n))\)

When Input modification is not allowed

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
from collections import deque

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        rows = len(grid)
        cols = len(grid[0])
        visited = set()
        totalIslands = 0
        directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]

        def bfs(i, j) -> None:
            # add cell in the queue to process
            q = deque([(i, j)])
            # mark the cell as visited
            visited.add((i, j))
            while q:
                row, col = q.popleft()
                # explore in 4 directions
                for di, dj in directions:
                    nr = row + di
                    nc = col + dj

                    if 0 <= nr < rows and 0 <= nc < cols:  # within the boundaries
                        if grid[nr][nc] == "1" and (nr, nc) not in visited:
                            # check if its a land and is not visited then add it to queue and mark it as visited
                            visited.add((nr, nc))
                            q.append((nr, nc))

        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == "1" and (r, c) not in visited:
                    totalIslands += 1
                    bfs(r, c)

        return totalIslands
Modify

Replace the following in above BFS algorithm, when you can modify input

- visited = set()

- visited.add((i, j))
+ grid[r][c] = "v"

- visited.add((nr, nc))
+ grid[nr][nc] = "v"

Quick tip

  • Don't go for DFS Stick to BFS

  • Interviewers do not want you to modify the input array

  • Stick to BFS for interviews

Approach: DFS on Grid/Maze/2D Matrix

Time complexity: \(O(mn)\)

Space complexity: \(O(mn)\)

When input modification is allowed

Algorithm

To solve this problem, we'll use a depth-first search (DFS).

We'll iterate through each cell in the grid.

When we find a '1', we'll mark it as visited and explore all adjacent land cells using DFS. This process counts as one island. We'll do this for all cells in the grid.

The time complexity of this solution is \(O(m \cdot n)\), where m is the number of rows and n is the number of columns in the grid. That’s because we visit each cell once.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        rows = len(grid)
        cols = len(grid[0])
        totalIslands = 0    # answer

        def dfs(r, c) -> None:
            # check if current cell is out of bounds
            if (r < 0 or r >= rows or c < 0 or c >= cols):
                return

            if grid[r][c] != "1":  # not land ,could be water(0) or visted land(v)
                return

            grid[r][c] = "v"       # mark current land as visited

            # explore the neighbour
            dfs(r + 1, c)
            dfs(r - 1, c)
            dfs(r, c - 1)
            dfs(r, c + 1)

        # Iterate through all cells in the grid
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == "1":  # found land
                    dfs(r, c)
                    totalIslands += 1

        return totalIslands

Comments