PracHub
QuestionsPremiumLearningGuidesInterview PrepCoaches
|Home/Coding & Algorithms/Chalk

Compute rainwater accumulation on a height grid

Last updated: Apr 20, 2026

Quick Overview

This question evaluates understanding of grid-based graph traversal, flow simulation to local minima, and the ability to reason about state propagation and accumulation across cells.

  • medium
  • Chalk
  • Coding & Algorithms
  • Software Engineer

Compute rainwater accumulation on a height grid

Company: Chalk

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

## Mountain Rainfall Accumulation You are given an `m x n` 2D integer grid `elevation`, where `elevation[r][c]` is the terrain height at cell `(r, c)`. Assume **1 unit** of rain falls on **each cell** (uniformly). Water from a cell flows **downhill** by repeatedly moving to a neighboring cell with **strictly lower** elevation until it reaches a **local minimum** (a cell that has no strictly lower neighbor). - Neighbors are the 4 orthogonal cells: up, down, left, right (when in bounds). - From a cell, water moves to the neighbor that represents the **steepest descent**. You may implement this as moving to the neighbor with the **minimum elevation** among all strictly lower neighbors. - If there are multiple equally-steep choices (ties), you may break ties **arbitrarily**, so multiple different correct outputs may exist. ### Task Return an `m x n` integer grid `accum` where: - `accum[r][c]` equals the **total number of rain units** that eventually end at cell `(r, c)` (including the unit that fell on `(r, c)` itself if it is a sink). - All non-sink cells should have `0` in `accum` (since they do not collect water permanently). ### Example **Input** ```text [ [3, 3, 1, -1], [2, 3, 3, 1], [0, 1, 3, 3] ] ``` **One valid output** ```text [ [0, 0, 0, 6], [0, 0, 0, 0], [6, 0, 0, 0] ] ``` **Another valid output** (due to tie-breaking) ```text [ [0, 0, 0, 7], [0, 0, 0, 0], [5, 0, 0, 0] ] ``` (There are 12 cells total, so the sum of all values in `accum` should be 12.)

Quick Answer: This question evaluates understanding of grid-based graph traversal, flow simulation to local minima, and the ability to reason about state propagation and accumulation across cells.

Related Interview Questions

  • Implement Python feature and resolver metaprogramming - Chalk (hard)
Chalk logo
Chalk
Feb 11, 2026, 12:00 AM
Software Engineer
Technical Screen
Coding & Algorithms
21
0
Loading...

Mountain Rainfall Accumulation

You are given an m x n 2D integer grid elevation, where elevation[r][c] is the terrain height at cell (r, c).

Assume 1 unit of rain falls on each cell (uniformly). Water from a cell flows downhill by repeatedly moving to a neighboring cell with strictly lower elevation until it reaches a local minimum (a cell that has no strictly lower neighbor).

  • Neighbors are the 4 orthogonal cells: up, down, left, right (when in bounds).
  • From a cell, water moves to the neighbor that represents the steepest descent . You may implement this as moving to the neighbor with the minimum elevation among all strictly lower neighbors.
  • If there are multiple equally-steep choices (ties), you may break ties arbitrarily , so multiple different correct outputs may exist.

Task

Return an m x n integer grid accum where:

  • accum[r][c] equals the total number of rain units that eventually end at cell (r, c) (including the unit that fell on (r, c) itself if it is a sink).
  • All non-sink cells should have 0 in accum (since they do not collect water permanently).

Example

Input

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

One valid output

[
  [0, 0, 0, 6],
  [0, 0, 0, 0],
  [6, 0, 0, 0]
]

Another valid output (due to tie-breaking)

[
  [0, 0, 0, 7],
  [0, 0, 0, 0],
  [5, 0, 0, 0]
]

(There are 12 cells total, so the sum of all values in accum should be 12.)

Comments (0)

Sign in to leave a comment

Loading comments...

Browse More Questions

More Coding & Algorithms•More Chalk•More Software Engineer•Chalk Software Engineer•Chalk 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.