Leetcode 200 - Number of Islands

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

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

Thought Process / Intuition

The intuition for this problem is to iterate through the grid, and when we encounter "1", we perform a DFS to mark all the connected lands as visited, by turning it into "0". We then increment the count of islands by 1. We repeat this process for all the cells in the grid.

Approach

Create a dfs function that takes in the row and column of the current cell, that will only be called if the cell is a land.
In the dfs function, mark the current cell as visited by turning it into "0".
Recursively call the dfs function on the adjacent cells (up, down, left, right) if they are lands.
Iterate through the grid and if the cell is a land, call the dfs function and increment the count of islands by 1.

Solution

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        def dfs(row, col):
            grid[row][col] = '0'
            for dx, dy in zip(directions[:-1], directions[1:]):
                # (-1, 0, 1, 0) and (0, 1, 0, -1)
                new_row, new_col = row + dx, col + dy
                if 0 <= new_row < rows and 0 <= new_col < cols and grid[new_row][new_col] == '1':
                    dfs(new_row, new_col)

        count = 0
        directions = (-1, 0, 1, 0, -1)
        rows, cols = len(grid), len(grid[0])
        for row in range(rows):
            for col in range(cols):
                if grid[row][col] == '1':
                    dfs(row, col)
                    count += 1
        return count

Complexity Analysis

Time complexity: $O(m * n)$

The time complexity is $O(m * n)$ , where m is the number of rows and n is the number of columns in the grid.
We iterate through each cell in the grid once to perform the DFS and mark the connected lands as visited.
Since each cell is visited at most once, the overall time complexity is still $O(m * n)$ .

Space complexity: $O(m * n)$

The space complexity is $O(m * n)$ . This worst-case space complexity occurs when the grid is filled with lands, and the DFS stack reaches a depth of $O(m * n)$ .

Shoutout to My Friends' Solutions

Kurt's Solution

Si Yuan's Solution