River Sizes

Tags

River Sizes

Category

Graphs

Difficulty

Medium

Problem Statement

Given a two-dimensional matrix of 0s and 1s, find the sizes of all "rivers" in the matrix. A river consists of any number of 1s that are either horizontally or vertically adjacent (not diagonally). Return an array of the sizes of all rivers in no particular order.

Intuition

This is a connected components problem on a grid. Each group of adjacent 1s forms a river, and we need to find the size of each group. We can use either BFS or DFS: start from any unvisited 1, explore all connected 1s (marking them as visited), count them, and record the size. Repeat until all cells have been processed.

Approach

  1. Create a visited matrix of the same dimensions, initialized to false.
  2. Initialize an empty list sizes to store river sizes.
  3. Iterate through every cell in the matrix: a. If the cell is 1 and not visited, start a BFS/DFS from it. b. During the traversal, mark all connected 1s as visited and count them. c. Append the count to sizes.
  4. Return sizes.

Pseudocode

function riverSizes(matrix):
    visited = 2D array of same size, all false
    sizes = []

    for i from 0 to rows - 1:
        for j from 0 to cols - 1:
            if visited[i][j]:
                continue
            if matrix[i][j] == 1:
                size = explore(matrix, visited, i, j)
                sizes.append(size)

    return sizes

function explore(matrix, visited, i, j):
    size = 0
    queue = [(i, j)]
    visited[i][j] = true

    while queue is not empty:
        (row, col) = queue.dequeue()
        size += 1
        for (newRow, newCol) in neighbors(row, col):
            if inBounds(newRow, newCol, matrix)
               and not visited[newRow][newCol]
               and matrix[newRow][newCol] == 1:
                visited[newRow][newCol] = true
                queue.enqueue((newRow, newCol))

    return size

Time & Space Complexity

  • Time: O(n * m), where n and m are the dimensions of the matrix. Each cell is visited at most once.
  • Space: O(n * m) for the visited matrix. The BFS queue can hold at most O(n * m) elements in the worst case.

Key Insights

  • This is the same pattern as counting islands or finding connected components in a grid.
  • Marking cells as visited (or modifying them in-place to 0) prevents double-counting.
  • BFS and DFS both work equally well; BFS uses a queue, DFS uses the call stack or an explicit stack.
  • Modifying the matrix in-place (setting visited 1s to 0) eliminates the need for a separate visited matrix.

Edge Cases

  • Matrix with all 0s: return an empty list.
  • Matrix with all 1s: return a single river of size n * m.
  • Each 1 is isolated (no adjacent 1s): return a list of 1s.
  • Single row or single column matrix.
  • Matrix with a single cell.

Linked mentions