Leetcode 200. Number of Islands

Problem

You are given a 2D grid representing a map where each cell contains either "1" (land) or "0" (water). An island is defined as a group of adjacent land cells connected horizontally or vertically (not diagonally). The grid is completely surrounded by water on all edges.

Your task is to count the total number of distinct islands in the grid.

Requirements

1. Two land cells are considered part of the same island if they share an edge (4-directional connectivity)
2. Diagonal connections do not count as adjacent
3. You must count each separate island exactly once
4. The input grid will not be modified in the actual test environment (though you may modify it in your solution if needed)

Constraints

• 1 <= grid.length <= 300 (number of rows)
• 1 <= grid[0].length <= 300 (number of columns)
• grid[i][j] is either "1" or "0"
• Time complexity should be O(m × n) where m and n are the grid dimensions
• Space complexity should be O(m × n) in the worst case

Examples

Example 1:

Input: grid = [ ["1","1","0","0"], ["1","1","0","0"], ["0","0","1","0"], ["0","0","0","1"] ] Output: 3 Explanation: The grid contains three separate islands. The first island is the 2×2 block of land in the top-left corner. The second is a single cell at row 2, column 2. The third is a single cell at row 3, column 3.

Example 2:

Input: grid = [ ["1","0","1","0","1"], ["0","0","0","0","0"], ["1","0","1","0","1"] ] Output: 6 Explanation: Six isolated single-cell islands exist, arranged in a pattern with water separating each one.

Example 3:

Input: grid = [ ["1","1","1"], ["0","1","0"], ["1","1","1"] ] Output: 1 Explanation: All land cells are connected through the center cell, forming one large cross-shaped island.

Hint 1: Graph Traversal Think of this as a graph problem where each land cell is a node, and edges exist between horizontally or vertically adjacent land cells. You need to count the number of connected components in this graph.

Hint 2: Marking Visited Cells When you discover an island, you need a way to mark all its cells as visited so you don't count the same island multiple times. Consider using depth-first search (DFS) or breadth-first search (BFS) to explore all cells belonging to one island.

Hint 3: Iteration Strategy Iterate through every cell in the grid. When you encounter an unvisited land cell, it represents a new island. Launch a traversal from that cell to mark all connected land cells, then increment your island counter.

Full Solution ` def countIslands(grid): if not grid or not grid[0]: return 0

rows = len(grid)
cols = len(grid[0])
island_count = 0

def dfs(r, c):
    # Base cases: out of bounds or water cell
    if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] == "0":
        return
    
    # Mark current cell as visited by changing it to water
    grid[r][c] = "0"
    
    # Explore all 4 adjacent cells (up, down, left, right)
    dfs(r - 1, c)  # up
    dfs(r + 1, c)  # down
    dfs(r, c - 1)  # left
    dfs(r, c + 1)  # right

# Iterate through every cell in the grid
for r in range(rows):
    for c in range(cols):
        # When we find unvisited land, it's a new island
        if grid[r][c] == "1":
            island_count += 1
            # Mark all cells of this island as visited
            dfs(r, c)

return island_count

`

Approach:

The solution uses depth-first search (DFS) to solve this connected-components problem:

1. Iterate through the grid: We examine each cell systematically using nested loops.
2. Detect new islands: When we encounter a land cell ("1"), we've found a new island (or the first cell of a new island), so we increment our counter.
3. Mark the entire island: We launch a DFS traversal from that cell to visit and mark all connected land cells. This prevents counting the same island multiple times.
4. DFS traversal: The recursive DFS function explores all four directions (up, down, left, right) from each land cell, marking visited cells by changing them to water ("0").
5. Return the count: After processing all cells, we return the total number of islands found.

Alternative Approach (BFS):

Instead of DFS, you could use BFS with a queue. The logic remains the same: when you find unvisited land, increment the counter and use BFS to mark all connected cells.

Complexity Analysis:

• Time Complexity: O(m × n) where m is the number of rows and n is the number of columns. In the worst case, we visit every cell once during the main iteration, and the DFS/BFS may visit each cell once more.
• Space Complexity: O(m × n) in the worst case. For DFS, the recursion stack could be as deep as the total number of cells if the entire grid is one large island arranged in a snake pattern. For BFS, the queue could hold all cells in a worst-case scenario.

Note: This solution modifies the input grid. If you need to preserve the original grid, you can create a separate visited set or a boolean matrix to track which cells have been explored.