PracHub
QuestionsPremiumLearningGuidesInterview PrepNEWCoaches
|Home/Coding & Algorithms/Amazon

Find all cells reachable by downhill flow

Last updated: Mar 29, 2026

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.

  • easy
  • Amazon
  • Coding & Algorithms
  • Software Engineer

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.

Related Interview Questions

  • Count Connected Components in an Undirected Graph - Amazon (medium)
  • Find Unique Target-Sum Pairs - Amazon (easy)
  • Find Valid IP Addresses in Files - Amazon (medium)
  • Implement Optimal Bucket Batching - Amazon (hard)
  • Implement Cache and Rotate Matrix - Amazon (medium)
Amazon logo
Amazon
Oct 18, 2025, 12:00 AM
Software Engineer
Technical Screen
Coding & Algorithms
4
0

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).

Comments (0)

Sign in to leave a comment

Loading comments...

Browse More Questions

More Coding & Algorithms•More Amazon•More Software Engineer•Amazon Software Engineer•Amazon Coding & Algorithms•Software Engineer Coding & Algorithms
PracHub

Master your tech interviews with 7,500+ real questions from top companies.

Product

  • Questions
  • Learning Tracks
  • Interview Guides
  • Resources
  • Premium
  • For Universities
  • Student Access

Browse

  • By Company
  • By Role
  • By Category
  • Topic Hubs
  • SQL Questions
  • Compare Platforms
  • Discord Community

Support

  • support@prachub.com
  • (916) 541-4762

Legal

  • Privacy Policy
  • Terms of Service
  • About Us

© 2026 PracHub. All rights reserved.