LeetCode 200: Number of Islands

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.

Constraints

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

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

Solution 1: Depth-First Search (DFS)

Thought

We can use the DFS technique to traverse the entire grid. Whenever we encounter land, we can mark all other connected lands (if the question doesn’t allow changing the initial grid, you can use a hash set to keep track) and continue to count how many independent islands have been traversed in total.

Steps

1. Use the DFS technique to traverse each element in the grid. If the current element is '1', increment num_islands by 1, and then call dfs_helper with the current coordinates as input parameters.
2. In the dfs_helper function:
   1. Base Case: If the current coordinates are out of the grid‘s range or the current element is not '1', terminate the current call.
   2. If not, mark the current element as '#' to indicate that it has been visited.
   3. Recursively call dfs_helper with the four coordinates adjacent to the current position as parameters.
3. After the traversal is complete, return the num_islands.

Codes

def num_islands(grid: List[List[str]]) -> int:
    m = len(grid)
    n = len(grid[0])
    num_islands = 0

    def dfs_helper(i: int, j: int) -> None:
        if i < 0 or i >= m or j < 0 or j >= n or grid[i][j] != '1':
            return

        grid[i][j] = '#'
        dfs_helper(i + 1, j)
        dfs_helper(i - 1, j)
        dfs_helper(i, j + 1)
        dfs_helper(i, j - 1)

    for i in range(m):
        for j in range(n):
            if grid[i][j] == '1':
                num_islands += 1
                dfs_helper(i, j)

    return num_islands

Complexities

• Time Complexity: O(MN),  where N is the width of the grid and M is the length of the grid.
• Space Complexity: O(MN),  where N is the width of the grid and M is the length of the grid.

Solution 2: Breadth-First Search (BFS)

Thought

Similar to the DFS approach described above, we can also use BFS to traverse the entire grid. The only difference is that we don’t need to define a recursive helper function to extend to all other connected lands with the current land. Instead, we use a queue to expand outward. Using a queue for BFS search is a classic technique.

Steps

1. Using the BFS technique to traverse each element in the grid:
   1. If the current element is not '1', skip the current iteration.
   2. If not, increment num_islands by 1, and then push the current coordinates (i, j)to the queue as the initial starting point.
   3. While the queue is not empty, continue to pop out coordinates from the front of the queue. If the popped coordinates are within the grid‘s range and the corresponding element is '1', mark it as '#' and push the four adjacent coordinates at the end of the queue in order.
2. After the traversal is complete, return the num_islands.

Codes

def num_islands(grid: List[List[str]]) -> int:
    m = len(grid)
    n = len(grid[0])
    num_islands = 0

    for i in range(m):
        for j in range(n):
            if grid[i][j] != '1':
                continue

            num_islands += 1
            queue = [(i, j)]
            while queue:
                (x, y) = queue.pop()
                if 0 <= x < m and 0 <= y < n and grid[x][y] == '1':
                    grid[x][y] = '#'
                    queue += [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]

    return num_islands

Complexities

• Time Complexity: O(MN),  where N is the width of the grid and M is the length of the grid.
• Space Complexity: O(MN),  where N is the width of the grid and M is the length of the grid.

References

• LeetCode link: Number of Islands – LeetCode