Counting Islands

Problem Description

Given a 2D grid map of '1's (land) and '0's (water), count 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.

For example, consider the following grid:

This grid has 1 island.

Now, consider this grid:

This grid has 3 islands.

Your task is to write a function that takes a 2D grid (represented as a list of lists of characters) as input and returns the number of islands in the grid.

Constraints:

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

Naive Solution

A naive solution would involve iterating through each cell of the grid and, upon encountering a '1' (land), incrementing the island count and then using either Depth-First Search (DFS) or Breadth-First Search (BFS) to explore and "sink" the entire island by marking all connected '1's as visited (e.g., changing them to '0's or some other marker).

This approach ensures that each island is counted only once.

def num_islands_naive(grid):
    if not grid:
        return 0

    rows, cols = len(grid), len(grid[0])
    num_islands = 0

    def dfs(row, col):
        if row < 0 or row >= rows or col < 0 or col >= cols or grid[row][col] == '0':
            return

        grid[row][col] = '0'  # Mark as visited
        dfs(row + 1, col)
        dfs(row - 1, col)
        dfs(row, col + 1)
        dfs(row, col - 1)

    for i in range(rows):
        for j in range(cols):
            if grid[i][j] == '1':
                num_islands += 1
                dfs(i, j)

    return num_islands

Optimal Solution

The optimal solution is essentially the same as the naive approach, leveraging DFS or BFS to efficiently explore and mark visited islands. The key is to ensure that the space complexity remains manageable, which DFS inherently does well. The core improvement lies in the clarity and conciseness of the code and ensuring no redundant operations are performed.

def num_islands(grid):
    if not grid:
        return 0

    rows, cols = len(grid), len(grid[0])
    num_islands = 0

    def sink(row, col):
        if 0 <= row < rows and 0 <= col < cols and grid[row][col] == '1':
            grid[row][col] = '0'
            sink(row + 1, col)
            sink(row - 1, col)
            sink(row, col + 1)
            sink(row, col - 1)

    for i in range(rows):
        for j in range(cols):
            if grid[i][j] == '1':
                num_islands += 1
                sink(i, j)

    return num_islands

Big(O) Runtime Analysis

The runtime 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, which takes O(M * N) time.
For each island encountered, we perform a DFS (or BFS) to "sink" the island. In the worst case, an island could cover the entire grid, requiring O(M * N) time to explore. However, each cell is visited at most once during the entire process because it is marked as visited ('0') when it is encountered.

Therefore, the overall runtime complexity is dominated by the initial grid traversal, resulting in O(M * N).

Big(O) Space Usage Analysis

The space complexity is O(M * N) in the worst case, due to the call stack of the DFS.

In the worst-case scenario, the entire grid is one large island. The DFS could potentially visit every cell, leading to a recursive call stack depth proportional to the number of cells. Each call adds a new frame to the stack, leading to O(M * N) space usage. Although, in most cases it will be less than O(M*N) as there won't be a single island occupying the whole grid.
The algorithm modifies the input grid in-place by changing '1's to '0's, but it doesn't use any other significant auxiliary data structures.

Thus, the space complexity is O(M * N).

Edge Cases

Empty Grid: If the input grid is empty (i.e., grid is None or has zero rows or columns), the function should return 0.
Grid with No Islands: If the grid contains only '0's, the function should return 0.
Grid with Only One Island: If the grid contains only '1's, representing a single island occupying the entire grid, the function should return 1.
Island Touching the Edges: The problem statement assumes the grid is surrounded by water. The solution handles cases where an island touches the edges correctly because the DFS/BFS exploration stops when it goes out of bounds.
Invalid Input: While the constraints specify that grid[i][j] is either '0' or '1', handling other characters in the grid might be considered for a more robust solution. We can raise an exception or ignore invalid characters.

These edge cases are addressed in the provided code by checking for an empty grid and ensuring the DFS/BFS exploration includes boundary checks.

Given a 2D grid of land and water, count the number of islands. Islands are connected horizontally or vertically. Assume edges are surrounded by water. Provide example grids to illustrate the expected output based on connected components of '1's in the grid.