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.

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.

Hints

  1. 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.
  2. 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.

Loading coding console...