How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a easy difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Amazon.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Amazon during technical interviews.

Find all cells reachable by downhill flow

Company: Amazon

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: easy

Interview Round: Technical Screen

## Problem You are given an `m x n` grid `heights`, where `heights[r][c]` is the elevation of cell `(r, c)`. A drop of water is placed at a starting cell `start = (sr, sc)`. From a cell, water may flow to any of its **4-directional neighbors** (up/down/left/right) **only if the neighbor has strictly lower height** than the current cell. A cell is considered **wet** if water can reach it by repeatedly flowing according to the rule above (including the start cell). ### Task Return the list (or set) of all wet cells. ### Input - `heights`: 2D integer array of size `m x n` - `start`: two integers `(sr, sc)` with `0 <= sr < m`, `0 <= sc < n` ### Output - All coordinates `(r, c)` that become wet. ### Notes / Constraints - You may return cells in any order. - Assume `m, n` can be up to a few thousand (so your approach should be near-linear in grid size in the worst case). - Heights can be any integers (not necessarily unique).

Quick Answer: This question evaluates graph traversal and reachability reasoning on a 2D elevation grid, testing algorithmic problem-solving, complexity analysis, and handling of monotonic flow constraints.

You are given an `m x n` grid `heights`, where `heights[r][c]` is the elevation of cell `(r, c)`. A drop of water is placed at a starting cell `start = (sr, sc)`. From a cell, water may flow to any of its 4-directional neighbors (up, down, left, right) only if the neighbor has strictly lower height than the current cell. A cell is considered wet if water can reach it by repeatedly flowing according to this rule (the start cell is always wet). Return the list of all wet cells as `[r, c]` pairs. You may return them in any order; for these tests, return them sorted in ascending (row, col) order. Constraints: - `0 <= sr < m`, `0 <= sc < n` - Heights can be any integers and are not necessarily unique. - `m, n` can be up to a few thousand, so aim for a near-linear-in-grid-size solution.

Constraints

0 <= sr < m, 0 <= sc < n
Heights are arbitrary integers (may be negative, may repeat).
Water flows only to a strictly lower neighbor (equal heights do not flow).
The start cell is always wet.
m, n can be up to a few thousand; target near-linear time.

Examples

Input: ([[5,4,3],[6,1,2],[7,8,9]], (0,0))

Expected Output: [[0, 0], [0, 1], [0, 2], [1, 1], [1, 2]]

Explanation: From (0,0)=5: right to 4 then 3; down-diagonally water reaches 1 at (1,1) via 4->1, and 2 at (1,2) via 3->2. The 6/7/8/9 block (all >= current) are never lower, so the bottom-left and corner stay dry.

Input: ([[1,2,3],[8,9,4],[7,6,5]], (1,1))

Expected Output: [[0, 0], [0, 1], [0, 2], [1, 0], [1, 1], [1, 2], [2, 0], [2, 1], [2, 2]]

Explanation: Start at the peak 9 in the center. Every other cell is reachable by a strictly-decreasing path spiraling outward (9->8->7->...->1 and 9->4->3->2->1, etc.), so the entire grid becomes wet.

Input: ([[5]], (0,0))

Expected Output: [[0, 0]]

Explanation: A single cell; only the start is wet.

Input: ([[3,3,3],[3,3,3],[3,3,3]], (1,1))

Expected Output: [[1, 1]]

Explanation: All heights equal. Since flow requires a strictly lower neighbor, water never leaves the start cell.

Input: ([[9,8,7,6,5]], (0,0))

Expected Output: [[0, 0], [0, 1], [0, 2], [0, 3], [0, 4]]

Explanation: A single monotonically decreasing row; water flows all the way to the right, wetting every cell.

Input: ([[10,1],[2,3]], (0,0))

Expected Output: [[0, 0], [0, 1], [1, 0]]

Explanation: From 10, water reaches 1 (right) and 2 (down). The cell 3 at (1,1) is higher than both 1 and 2, so it is never reached and stays dry.

Input: ([[-1,-2,-3],[-4,-5,-6]], (0,0))

Expected Output: [[0, 0], [0, 1], [0, 2], [1, 0], [1, 1], [1, 2]]

Explanation: Negative heights work the same way: -1 > -2 > -3 and -4 > -5 > -6 with each top cell above the one below, so flow reaches every cell.

Hints

This is a directed flood-fill: from each cell you may only move to a strictly-lower 4-directional neighbor. Because every move strictly decreases height, you can never revisit a cell, so a single BFS or DFS from the start visits each reachable cell exactly once.
Equal heights block flow (the rule is strictly lower). Mark cells visited when you enqueue them to avoid duplicates, and collect every dequeued cell as wet.

Quick Overview

This question evaluates graph traversal and reachability reasoning on a 2D elevation grid, testing algorithmic problem-solving, complexity analysis, and handling of monotonic flow constraints.