Waterfall Streams

Tags

Waterfall Streams

Category

Arrays

Difficulty

Very Hard

Problem Statement

You are given a two-dimensional array representing a landscape of blocks and empty spaces. Water is poured from a specific position at the top row and flows downward due to gravity. When water hits a block, it splits equally to the left and right, continuing to flow along the surface of the block until it can fall again or reaches a wall. Simulate this process row by row and return the distribution of water in the bottom row as percentages.

Intuition

This problem is a simulation. Water flows downward when there is empty space below, and spreads horizontally when blocked. The key insight is to process the grid row by row from top to bottom. At each row, we know how much water arrives at each column. If the cell below is empty, the water falls through. If the cell below is a block, the water splits and flows left and right along the block surface until it finds an opening to fall or is stopped by a wall. When water splits, each side gets exactly half. This halving compounds at every split.

Approach

  1. Initialize a "water row" representing the percentage of water at each column position. Set 100% at the source column in the top row.
  2. For each row (from top to bottom): a. Create a new water row initialized to zeros. b. For each column with water in the current water row:
    • If the cell directly below is empty (0), the water falls straight down into that column in the new water row.
    • If the cell directly below is a block (1), split the water equally (50/50) and try to flow left and right. c. When flowing left or right along a block surface:
    • Move in that direction. If the next cell in the current row is a block, the water is trapped and lost.
    • If the next cell is empty and the cell below it is also empty, the water falls into that column of the new water row.
    • If the next cell is empty but the cell below is a block, continue flowing in the same direction with the same amount.
  3. After processing all rows, the final water row gives the bottom-row water distribution.

Pseudocode

function waterfallStreams(array, source):
    waterRow = array of zeros, length = number of columns
    waterRow[source] = 100.0

    for row from 0 to len(array) - 2:
        newWaterRow = array of zeros

        for col from 0 to len(waterRow) - 1:
            if waterRow[col] == 0:
                continue
            water = waterRow[col]

            if array[row + 1][col] == 0:  # empty below
                newWaterRow[col] += water
            else:  # block below, split and flow sideways
                halfWater = water / 2.0

                # Flow left
                flowSideways(array, row, col, -1, halfWater, newWaterRow)
                # Flow right
                flowSideways(array, row, col, +1, halfWater, newWaterRow)

        waterRow = newWaterRow

    return waterRow

function flowSideways(array, row, col, direction, water, newWaterRow):
    nextCol = col + direction
    while nextCol >= 0 and nextCol < numCols:
        if array[row][nextCol] == 1:  # wall in the way
            break
        if array[row + 1][nextCol] == 0:  # can fall
            newWaterRow[nextCol] += water
            break
        nextCol += direction  # keep sliding

Time & Space Complexity

  • Time: O(w^2 * h) in the worst case, where w is the width and h is the height. For each cell with water in each row, sideways flow can traverse up to w columns. In practice, the total work is often much less.
  • Space: O(w) for the water row arrays.

Key Insights

  • Process row by row, treating each row as an independent subproblem given the water distribution arriving from above.
  • Water that hits a block splits equally; this halving is the central mechanic.
  • When flowing sideways, water stops at walls (blocks in the same row) and falls at openings (empty cells with empty space below).
  • Water that flows sideways over a block but cannot find an opening is simply lost (absorbed by the walls).
  • The simulation naturally handles arbitrary cascading because each row feeds into the next.

Edge Cases

  • Water source is directly above a column of empty space: 100% of water ends up in that column at the bottom.
  • Water hits a flat, unbroken floor with no gaps: it flows to the edges and is lost.
  • Single-column grid: water either falls straight through or is blocked entirely.
  • Water splits repeatedly: percentages can become very small fractions, so use floating-point arithmetic.
  • Blocks in the top row next to the source: water cannot flow through them and that portion is lost immediately.
  • The source column itself contains a block in the first row: typically the source is placed at an empty cell.

Linked mentions