Problem Brief

Simulate Water Flow

INTERNOA

See the Image Source section at the very bottom of the page for the original problem statement 🐼

Civil engineers are using a digital elevation model to simulate how rainfall flows over terrain, represented as a 2D grid of integers where each number indicates the elevation at that point. The water starts flowing from a specific location, given by two coordinates (startRow, startCol), and moves to neighboring cells—up, down, left, or right—if the next cell's height is less than or equal to the current one. The water continues flowing until it can no longer move to any lower or equal elevation. Your task is to track this process by returning a new 2D grid, where each cell shows the time step when it first becomes wet, starting from 0 at the water's initial point. If a cell never gets wet, mark it as -1. The challenge is to design an efficient solution that works within a reasonable time limit, as water flow simulations can involve large terrain grids.

🦋 Thanks to Charlotte baby 🦋

1Example 1

Input

heights = [[3, 2, 1], [6, 5, 4], [9, 8, 7]], startRow = 1, startCol = 1

Output

[[-1, 1, 2], [-1, 0, 1], [-1, -1, -1]]

Explanation

Unfortunately, we dont have the access to the video that explain why the expected output should be what it is rn. The terrain consists of a single cell. The starting point is this cell, so it becomes wet at time 0.

2Example 2

Input

heights = [[10, 10, 10, 10], [10, 10, 10, 10], [10, 10, 10, 10], [10, 10, 10, 10]], startRow = 1, startCol = 2

Output

[[3, 2, 1, 2], [2, 1, 0, 1], [3, 2, 1, 2], [4, 3, 2, 3]]

Explanation

Water starts at cell (1, 2) and can flow to (imcomplete..will add once find more reliable source) Unfortunately, again, we dont have the access to the video explanation 🥲 Water begins its journey at cell (1, 1) and spreads to neighboring cells with lower heights. The flow continues until there are no more adjacent cells that can be reached from the current wet cells. Each cell records the time step when it first becomes wet, with smaller numbers indicating earlier steps in the flow. The simulation halts when the water can no longer move. (This explanation might be incomplete, and I'll provide more details once I find a reliable source.)

Constraints

Limits and guarantees your solution can rely on.

🍊🍊