River Sizes

This challenge aims to come up with a solution that implements an algorithm to find the sizes of rivers in a 2D matrix.

Problem

Given a 2D matrix representing land with 0s and 1s for water(river), the problem is to find the sizes of all rivers (adjacent 1s) in the matrix.

# O(nm) time | O(nm) space where n -row of matrix and m is column of the matrix
def river_sizes(matrix):
    """
    Finds the sizes of rivers in a 2D matrix representing land.

    Args:
        matrix (list of list): A 2D matrix where 0 represents water and 1 represents land.

    Returns:
        list: A list containing the sizes of all rivers in the matrix.

    Example:
        matrix = [
            [1, 0, 0, 1, 0],
            [1, 0, 1, 0, 0],
            [0, 0, 1, 0, 1],
            [1, 0, 1, 0, 1],
            [1, 0, 1, 1, 0]
        ]
        river_sizes(matrix)  # Output: [1, 2, 2, 2, 5]
    """
    sizes = []
    visited = [[False for _ in row] for row in matrix]

    # Iterate through each cell in the matrix
    for i in range(len(matrix)):
        for j in range(len(matrix[i])):
            # If the cell is visited, continue to the next cell
            if visited[i][j]:
                continue
            # Explore the river starting from the current cell
            traverse_node(i, j, matrix, visited, sizes)
    return sizes


def traverse_node(i, j, matrix, visited, sizes):
    """
    Traverses a river starting from the given cell and updates its size.

    Args:
        i (int): Row index of the current cell.
        j (int): Column index of the current cell.
        matrix (list of list): The 2D matrix representing land.
        visited (list of list): Boolean array to track visited cells.
        sizes (list): List to store the sizes of rivers.

    Example:
        traverse_node(0, 0, matrix, visited, sizes)
    """
    current_river_size = 0
    nodes_to_explore = [[i, j]]

    # Explore the river using DFS
    while nodes_to_explore:
        current_node = nodes_to_explore.pop()
        i, j = current_node[0], current_node[1]
        # If the cell is visited, continue to the next node
        if visited[i][j]:
            continue
        visited[i][j] = True
        # If the cell contains water, continue to the next node
        if matrix[i][j] == 0:
            continue
        current_river_size += 1
        # Get unvisited neighboring cells and add them to the list of nodes to explore
        unvisited_neighbors = get_unvisited_neighbors(i, j, matrix, visited)
        for neighbor in unvisited_neighbors:
            nodes_to_explore.append(neighbor)
    # If the river size is greater than 0, add it to the sizes list
    if current_river_size > 0:
        sizes.append(current_river_size)


def get_unvisited_neighbors(i, j, matrix, visited):
    """
    Returns a list of unvisited neighboring cells of the given cell.

    Args:
        i (int): Row index of the current cell.
        j (int): Column index of the current cell.
        matrix (list of list): The 2D matrix representing land.
        visited (list of list): Boolean array to track visited cells.

    Returns:
        list: A list of unvisited neighboring cells.

    Example:
        get_unvisited_neighbors(1, 1, matrix, visited)
    """
    unvisited_neighbors = []
    # Check neighboring cells for unvisited land cells
    if i > 0 and not visited[i - 1][j]:
        unvisited_neighbors.append([i - 1, j])
    if i < len(matrix) - 1 and not visited[i + 1][j]:
        unvisited_neighbors.append([i + 1, j])
    if j > 0 and not visited[i][j - 1]:
        unvisited_neighbors.append([i, j - 1])
    if j < len(matrix[0]) - 1 and not visited[i][j + 1]:
        unvisited_neighbors.append([i, j + 1])
    return unvisited_neighbors

Approach

1. Initialize an empty list sizes to store the sizes of rivers.
2. Initialize a 2D boolean array visited to keep track of visited cells in the matrix.
3. Iterate through each cell (i, j) in the matrix:
   • If the cell (i, j) is visited, continue to the next cell.
   • Otherwise, call the traverse_node function to explore the river starting from cell (i, j).
4. In the traverse_node function:
   • Initialize current_river_size to 0 and nodes_to_explore as a list containing the current cell.
   • While there are nodes to explore:
     • Pop a node from nodes_to_explore.
     • If the node is visited, continue to the next node.
     • In case the node is not visited, mark the node as visited.
     • If the cell contains land (0), continue to the next node because that does not count.
     • Increment current_river_size.
     • Get unvisited neighboring cells of the current cell and add them to nodes_to_explore.
   • If current_river_size is greater than 0, append it to the sizes list.
5. The get_unvisited_neighbors function returns a list of unvisited neighboring cells of a given cell.

Time Complexity

Traversing Cells: We traverse each cell in the 2D matrix exactly once. This traversal involves a nested loop, resulting in a time complexity of O(n×m), where n is the number of rows and m is the number of columns in the matrix.

DFS for Each River: For each unvisited land cell encountered, we perform a depth-first search (DFS) to explore the river connected to that cell. In the worst case, the DFS can visit all cells of a river, leading to a time complexity of O(n×m) for each river.

Since we perform DFS for each river, the total time complexity is O(n×m) multiplied by the number of rivers.

Overall Time Complexity: Considering all the steps, the overall time complexity of the solution is O(n×m), where n is the number of rows and m is the number of columns in the matrix.

Space Complexity

Visited Array: We use a boolean matrix visited to track visited cells in the matrix. Its size is the same as the input matrix. Therefore, the space complexity for the visited array is O(n×m).

Recursive Stack (DFS): The depth-first search (DFS) algorithm used to traverse each river may lead to recursion and consume additional space on the call stack.

The maximum depth of the recursion stack is limited by the size of the river, but in the worst case, it can be as large as the number of cells in the matrix (O(n×m).

Overall Space Complexity: Considering both the visited array and the recursion stack, the overall space complexity of the solution is O(n×m).

Use Case

This algorithm can be used in geographical analysis, such as identifying river networks or water bodies within a given area represented by a matrix.

Unit Tests

Here are some unit tests using Python's unittest module to test the correctness and robustness of the river_sizes function:

import unittest


class TestRiverSizes(unittest.TestCase):
    def test_example_case(self):
        # Example matrix from the problem statement
        matrix = [
            [1, 0, 0, 1, 0],
            [1, 0, 1, 0, 0],
            [0, 0, 1, 0, 1],
            [1, 0, 1, 0, 1],
            [1, 0, 1, 1, 0]
        ]
        expected_sizes = [1, 2, 2, 2, 5]
        self.assertEqual(sorted(river_sizes(matrix)), sorted(expected_sizes))

    def test_single_cell_river(self):
        # Single cell river
        matrix = [[1]]
        expected_sizes = [1]
        self.assertEqual(river_sizes(matrix), expected_sizes)

    def test_single_row_river(self):
        # Single row with multiple rivers
        matrix = [[1, 0, 1, 0, 1]]
        expected_sizes = [1, 1, 1]
        self.assertEqual(river_sizes(matrix), expected_sizes)

    def test_single_column_river(self):
        # Single column with multiple rivers
        matrix = [[1], [0], [1], [0], [1]]
        expected_sizes = [1, 1, 1]
        self.assertEqual(river_sizes(matrix), expected_sizes)

    def test_empty_matrix(self):
        # Empty matrix
        matrix = []
        expected_sizes = []
        self.assertEqual(river_sizes(matrix), expected_sizes)

    def test_all_water(self):
        # All cells are water
        matrix = [
            [0, 0, 0],
            [0, 0, 0],
            [0, 0, 0]
        ]
        expected_sizes = []
        self.assertEqual(river_sizes(matrix), expected_sizes)

    def test_all_land(self):
        # All cells are land
        matrix = [
            [1, 1, 1],
            [1, 1, 1],
            [1, 1, 1]
        ]
        expected_sizes = [9]
        self.assertEqual(river_sizes(matrix), expected_sizes)


if __name__ == '__main__':
    unittest.main()

These unit tests cover various scenarios:

•     Example matrix from the problem statement.
•     Single-cell river.
•     Single row and single column matrices with multiple rivers.
•     Empty matrix.
•     Matrices with all cells as water or all cells as land.

Each test case asserts whether the river_sizes function returns the expected sizes of rivers for a given input matrix.

These tests help ensure the correctness and robustness of the solution.

Application

The algorithm efficiently traverses the matrix to identify connected regions of water (rivers) and computes their sizes.

It uses depth-first search (DFS) to explore each river and mark visited cells to avoid redundant exploration.