Problem Statement

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.

Additional information

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

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

Depth-First Search (DFS - Recursive)

Intuition

To find the number of islands, we can iterate through every single cell in the grid. Whenever we encounter a "1" (land), we know we have found the start of a new island! We can increment our island count by 1.

However, if we keep scanning the grid, we will hit the other parts of the same island and double-count them. To prevent this, we launch a Depth-First Search (DFS) the moment we find a "1". The DFS will explore all connected land horizontally and vertically. As it visits each piece of connected land, it "sinks" it by changing the "1" to a "0". This completely wipes the island off the map, ensuring we never count it again when our main loops continue scanning.

Algorithm

1. Check if the grid is empty. If so, return 0.
2. Store the dimensions ROWS and COLS.
3. Initialize an islands counter to 0.
4. Create a recursive helper function dfs(r, c).

• Base Case: If r or c are out of bounds, or if the current cell is "0" (water), return immediately.
• Sink the land: Change grid[r][c] to "0".
• Recurse: Call dfs on the 4 adjacent neighbors (up, down, left, right).

5. Loop through every row r and column c in the grid.
6. If grid[r][c] == "1", increment islands by 1 and call dfs(r, c) to sink the entire island.
7. Return the islands count.

def numIslands(grid: list[list[str]]) -> int:
    if not grid:
        return 0
        
    ROWS, COLS = len(grid), len(grid[0])
    islands = 0
    
    def dfs(r, c):
        # Base case: Out of bounds or water
        if r < 0 or c < 0 or r >= ROWS or c >= COLS or grid[r][c] == "0":
            return
            
        # Sink the island piece
        grid[r][c] = "0"
        
        # Explore neighbors
        dfs(r + 1, c)
        dfs(r - 1, c)
        dfs(r, c + 1)
        dfs(r, c - 1)
        
    for r in range(ROWS):
        for c in range(COLS):
            if grid[r][c] == "1":
                islands += 1
                dfs(r, c)
                
    return islands

Time & Space Complexity

• Time complexity: O(M * N)

• Reason: We iterate through every cell in the grid. Even though we run a DFS, each cell is visited at most twice (once by the main loop, and once by the DFS before being turned to "0").

• Space complexity: O(M * N)

• Reason: In the absolute worst-case scenario (where the entire grid is a single massive island), the recursion stack for the DFS will go M * N levels deep before starting to return.

Breadth-First Search (BFS - Iterative Optimal Space)

Intuition

While DFS is highly intuitive, recursive calls run the risk of causing a Stack Overflow on massive grids due to the deep call stack.

We can achieve the exact same "island sinking" logic using an iterative Breadth-First Search (BFS) with a Queue. Instead of diving deep into the island, BFS expands outward layer by layer like a ripple in a pond. When we find a "1", we put its coordinates in our queue, mark it as water, and then repeatedly pop cells from the queue and add their land neighbors. This prevents deep recursion.

Algorithm

1. Check if the grid is empty. If so, return 0.
2. Store the dimensions ROWS and COLS. Initialize islands = 0.
3. Create an iterative helper function bfs(r, c).

• Initialize a deque (queue) with the starting coordinates [(r, c)].
• Immediately mark the starting cell as "0".
• While the queue is not empty:
• Pop the front coordinates row, col.
• Check all 4 adjacent directions. If a neighbor is within bounds and is "1", add it to the queue and instantly mark it as "0".

4. Loop through every cell. If it's a "1", increment islands and call bfs(r, c).
5. Return islands.

def numIslands(grid: list[list[str]]) -> int:
    if not grid:
        return 0
        
    ROWS, COLS = len(grid), len(grid[0])
    islands = 0
    
    def bfs(r, c):
        q = deque()
        q.append((r, c))
        grid[r][c] = "0" # Mark visited immediately
        
        while q:
            row, col = q.popleft()
            directions = [[1, 0], [-1, 0], [0, 1], [0, -1]]
            
            for dr, dc in directions:
                nr, nc = row + dr, col + dc
                if (0 <= nr < ROWS and 0 <= nc < COLS and grid[nr][nc] == "1"):
                    q.append((nr, nc))
                    grid[nr][nc] = "0" 
                    
    for r in range(ROWS):
        for c in range(COLS):
            if grid[r][c] == "1":
                islands += 1
                bfs(r, c)
                
    return islands

Time & Space Complexity

• Time complexity: O(M * N)

• Reason: Just like DFS, every cell is visited and processed a constant number of times.

• Space complexity: O(min(M, N))

• Reason: The queue holds the coordinates of the "perimeter" of the island as BFS expands. In the worst case (a fully filled grid), the maximum perimeter length in a 2D grid is bounded by the diagonal, which takes proportional space O(min(M, N)). This makes iterative BFS far more memory-safe than recursive DFS.