Pour Water
Goldman SachsThe problem
You are given an elevation map represents as an integer array heights where heights[i] representing the height of the terrain at index i. The width at each index is 1. You are also given two integers volume and k. volume units of water will fall at index k.
Water first drops at the index k and rests on top of the highest terrain or water at that index. Then, it flows according to the following rules:
- If the droplet would eventually fall by moving left, then move left.
- Otherwise, if the droplet would eventually fall by moving right, then move right.
- Otherwise, rise to its current position. Here, "eventually fall" means that the droplet will eventually be at a lower level if it moves in that direction. Also, level means the height of the terrain plus any water in that column.
We can assume there is infinitely high terrain on the two sides out of bounds of the array. Also, there could not be partial water being spread out evenly on more than one grid block, and each unit of water has to be in exactly one block.
Input: heights = [2,1,1,2,1,2,2], volume = 4, k = 3 Output: [2,2,2,3,2,2,2] Explanation: The first drop of water lands at index k = 3. When moving left or right, the water can only move to the same level or a lower level. (By level, we mean the total height of the terrain plus any water in that column.) Since moving left will eventually make it fall, it moves left. (A droplet "made to fall" means go to a lower height than it was at previously.) Since moving left will not make it fall, it stays in place.
Input: heights = [1,2,3,4], volume = 2, k = 2 Output: [2,3,3,4] Explanation: The last droplet settles at index 1, since moving further left would not cause it to eventually fall to a lower height.
Input: heights = [3,1,3], volume = 5, k = 1
- 1 <= heights.length <= 100
- 0 <= heights[i] <= 99
- 0 <= volume <= 2000
- 0 <= k < heights.length
cpp
class Solution {
public:
vector<int> pourWater(vector<int>& heights, int volume, int k) {
// Your code goes here
}
};java
class Solution {
public int[] pourWater(int[] heights, int volume, int k) {
// Your code goes here
}
}python
class Solution(object):
def pourWater(self, heights, volume, k):
"""
:type heights: List[int]
:type volume: int
:type k: int
:rtype: List[int]
"""
# Your code goes herejavascript
/**
* @param {number[]} heights
* @param {number} volume
* @param {number} k
* @return {number[]}
*/
var pourWater = function(heights, volume, k) {
// Your code goes here
};csharp
public class Solution
{
public int[] PourWater(int[] heights, int volume, int k)
{
// Your code goes here
}
}go
func pourWater(heights []int, volume int, k int) []int {
// Your code goes here
}Stuck? Show a way to structure it+
- 01Treat heights as terrain plus already settled water.
- 02For each drop, walk left across non-increasing levels and remember the lowest position.
- 03If a strictly lower left position exists, increment it.
- 04Otherwise perform the symmetric right walk and use its lowest position.
- 05If neither side can fall, increment the original index.
Reference answer
Then expect these follow-ups
How would you test a flat plateau with lower basins on both sides?
Tests: follow-up reasoning
What optimization matters if volume becomes very large?
Tests: constraint adaptation
Free to read · better with Enzo
Practice this out loud with Enzo
Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.
Next question