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)
Examples
Input: ([2,1,1,2,1,2,2], 4, 3)
Expected Output: [2,2,2,3,2,2,2]
Explanation: The first two units fill the lower cells on the left, the third fills the lower cell on the right, and the last unit stays at K.
Input: ([3,1,1,2], 1, 3)
Expected Output: [3,2,1,2]
Explanation: Scanning left reaches indices 2 and 1, both with minimum height 1. The water must choose the leftmost minimum, index 1.
Input: ([2,1,1,3], 1, 0)
Expected Output: [2,1,2,3]
Explanation: There is no left side. On the right, indices 1 and 2 are both minimum reachable positions, so the water settles at the rightmost one, index 2.
Input: ([1,2,3], 0, 1)
Expected Output: [1,2,3]
Explanation: No water is poured, so the terrain stays unchanged.
Input: ([5], 3, 0)
Expected Output: [8]
Explanation: With only one column, every unit must settle at index 0.
Hints
- Simulate one water unit at a time. For each unit, scan left first, and only if that fails, scan right.
- When scanning, keep track of the best position seen so far. Updating the best index even on equal heights helps enforce the leftmost/rightmost tie-breaking.