Simulate pouring water onto terrain
Company: Airbnb
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
## Problem
You are given an integer array `heights` representing a 1D terrain (each index is a column height), an integer `V` (units of water), and an index `K` where water is poured.
Water is poured **one unit at a time** onto column `K`. For each unit:
1. It first tries to flow **left**: starting from `K`, move left while the next column is **not higher** than the current. Among all reachable positions on the left with the **minimum height**, the water settles at the **leftmost** such position.
2. If it cannot settle anywhere on the left (i.e., no strictly lower position than `heights[K]` was found by the left scan), it then tries to flow **right** symmetrically: move right while the next column is **not higher** than the current. Among all reachable positions on the right with the **minimum height**, the water settles at the **rightmost** such position.
3. If neither side offers a lower position, the water settles at `K`.
After placing all `V` units, return the resulting `heights` array.
## Input
- `heights`: array of non-negative integers
- `V`: non-negative integer (units of water)
- `K`: integer index (`0 <= K < len(heights)`)
## Output
- The final `heights` array after all water is poured.
## Notes
- Each water unit increases exactly one column height by `1`.
- The “scan” rules above must be followed precisely (tie-breaking included).
Quick Answer: This question evaluates a candidate's ability to implement a discrete simulation and perform array manipulation while correctly handling deterministic scan rules, tie-breaking, and boundary conditions.
You are given an integer array heights representing a 1D terrain, an integer V for the number of water units to pour, and an index K where each unit of water starts.
Water is poured one unit at a time. For each unit:
1. Try to flow left from K while the next column is not higher than the current one.
2. Among all reachable left positions with the minimum height, settle at the leftmost such position.
3. If no strictly lower position exists on the left, try the same process on the right.
4. Among all reachable right positions with the minimum height, settle at the rightmost such position.
5. If neither side has a strictly lower position, the water settles at K.
Each settled water unit increases exactly one column height by 1. Return the terrain after all V units have been poured.
Constraints
- 1 <= len(heights) <= 2000
- 0 <= heights[i] <= 10^9
- 0 <= V <= 2000
- 0 <= K < len(heights)