How should I practice Trace Every Water Drop to Its Resting Destination?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Google onsite interview problems in FastPrep.

Is Trace Every Water Drop to Its Resting Destination associated with Google?

FastPrep tags this as a Google onsite interview coding practice problem when the problem catalog has that company and stage context.

Trace Every Water Drop to Its Resting Destination

Google● MediumINTERNONSITE INTERVIEW

Problem statement

You are given an m x n integer matrix heights. Place one drop of water on every cell. A drop repeatedly considers the four orthogonally adjacent positions and moves to the position with the lowest height, but only when that height is strictly lower than its current cell.

A position immediately outside the grid has height 0. If a drop moves to such a position, it has left the grid and stops there. When several lowest positions have the same height, choose the one with the lexicographically smallest coordinate: compare the row first, then the column.

The problem statement continues

Pro

Examples

Example 1

heights = [[5,4,5],[4,-1,4],[5,4,5]]return = [[-1,0],[1,1],[-1,2],[1,1],[1,1],[1,1],[2,-1],[1,1],[2,3]]

The four edge-center cells descend into the basin at [1,1], as does the basin itself. Each positive corner sees two equally low outside positions of height 0 and uses the lexicographically smaller coordinate.

FastPrep Pro

Reported in 1 Google interview this week

Unlock this recently reported problem

FastPrep Pro gives you full access to interview problems reported within the last week.

Full problem statement and constraints
2 more worked examples, explained
Guided hints and editorial
Run your code on real test cases

$8.25/month

$99 billed yearly — or $19 month-to-month. Cancel anytime.

Free plan — 2 of 2 free unlocks used this week

See Google hiring insights