Pour Water | K5kC

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.

Examples

Example 1:

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. The next droplet falls at index k = 3. Since the new droplet moving left will eventually make it fall, it moves left. Notice that the droplet still preferred to move left, even though it could move right (and moving right makes it fall quicker.) The third droplet falls at index k = 3. Since moving left would not eventually make it fall, it tries to move right. Since moving right would eventually make it fall, it moves right. Finally, the fourth droplet falls at index k = 3. Since moving left would not eventually make it fall, it tries to move right. Since moving right would not eventually make it fall, it stays in place.

Example 2:

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.

Example 3:

Input: heights = [3,1,3], volume = 5, k = 1
Output: [4,4,4]

Constraints:

1 <= heights.length <= 100
0 <= heights[i] <= 99
0 <= volume <= 2000
0 <= k < heights.length

Solution

Method 1 - Simulation (Greedy Drop)

Intuition

Simulate the process for each droplet. For each unit of water, try to move left as far as possible to a lower height, then right, otherwise stay. Always prefer the leftmost possible position. Work with the input array heights, and parameters volume and k; track candidate indices with idx while scanning with i over n positions.

Approach

For each droplet (v from 0 to volume-1):

Initialize idx = k.
Try to move left: for i from k-1 down to 0, update idx to i if heights[i] < heights[idx]; stop when heights[i] > heights[idx].
If idx != k, place water at idx and continue to next droplet.
Otherwise, try to move right: for i from k+1 up to n-1, update idx to i if heights[i] < heights[idx]; stop when heights[i] > heights[idx].
Place water at idx (may be k).
Increase heights[idx] by 1 and repeat.

Complexity

⏰ Time complexity: O(volume * n)
🧺 Space complexity: O(1) (ignoring input/output).

Code

C++

#include <vector>
using namespace std;
vector<int> pourWater(vector<int>& heights, int volume, int k) {
    int n = heights.size();
    for (int v = 0; v < volume; ++v) {
        int idx = k;
        // Try left
        for (int i = k-1; i >= 0; --i) {
            if (heights[i] < heights[idx]) idx = i;
            else if (heights[i] > heights[idx]) break;
        }
        if (idx != k) { heights[idx]++; continue; }
        // Try right
        for (int i = k+1; i < n; ++i) {
            if (heights[i] < heights[idx]) idx = i;
            else if (heights[i] > heights[idx]) break;
        }
        heights[idx]++;
    }
    return heights;
}

Go

func pourWater(heights []int, volume int, k int) []int {
    n := len(heights)
    for v := 0; v < volume; v++ {
        idx := k
        // Try left
        for i := k-1; i >= 0; i-- {
            if heights[i] < heights[idx] {
                idx = i
            } else if heights[i] > heights[idx] {
                break
            }
        }
        if idx != k {
            heights[idx]++
            continue
        }
        // Try right
        for i := k+1; i < n; i++ {
            if heights[i] < heights[idx] {
                idx = i
            } else if heights[i] > heights[idx] {
                break
            }
        }
        heights[idx]++
    }
    return heights
}

Java

import java.util.*;
class Solution {
    public int[] pourWater(int[] heights, int volume, int k) {
        int n = heights.length;
        for (int v = 0; v < volume; ++v) {
            int idx = k;
            // Try left
            for (int i = k-1; i >= 0; --i) {
                if (heights[i] < heights[idx]) idx = i;
                else if (heights[i] > heights[idx]) break;
            }
            if (idx != k) { heights[idx]++; continue; }
            // Try right
            for (int i = k+1; i < n; ++i) {
                if (heights[i] < heights[idx]) idx = i;
                else if (heights[i] > heights[idx]) break;
            }
            heights[idx]++;
        }
        return heights;
    }
}

Kotlin

fun pourWater(heights: IntArray, volume: Int, k: Int): IntArray {
    val n = heights.size
    repeat(volume) {
        var idx = k
        for (i in k-1 downTo 0) {
            if (heights[i] < heights[idx]) idx = i
            else if (heights[i] > heights[idx]) break
        }
        if (idx != k) { heights[idx]++; return@repeat }
        for (i in k+1 until n) {
            if (heights[i] < heights[idx]) idx = i
            else if (heights[i] > heights[idx]) break
        }
        heights[idx]++
    }
    return heights
}

Python

def pourWater(heights: list[int], volume: int, k: int) -> list[int]:
    n = len(heights)
    for _ in range(volume):
        idx = k
        # Try left
        for i in range(k-1, -1, -1):
            if heights[i] < heights[idx]:
                idx = i
            elif heights[i] > heights[idx]:
                break
        if idx != k:
            heights[idx] += 1
            continue
        # Try right
        for i in range(k+1, n):
            if heights[i] < heights[idx]:
                idx = i
            elif heights[i] > heights[idx]:
                break
        heights[idx] += 1
    return heights

Rust

fn pour_water(mut heights: Vec<i32>, volume: i32, k: usize) -> Vec<i32> {
    let n = heights.len();
    for _ in 0..volume {
        let mut idx = k;
        for i in (0..k).rev() {
            if heights[i] < heights[idx] {
                idx = i;
            } else if heights[i] > heights[idx] {
                break;
            }
        }
        if idx != k {
            heights[idx] += 1;
            continue;
        }
        for i in k+1..n {
            if heights[i] < heights[idx] {
                idx = i;
            } else if heights[i] > heights[idx] {
                break;
            }
        }
        heights[idx] += 1;
    }
    heights
}

TypeScript

export function pourWater(heights: number[], volume: number, k: number): number[] {
    const n = heights.length;
    for (let v = 0; v < volume; ++v) {
        let idx = k;
        // Try left
        for (let i = k-1; i >= 0; --i) {
            if (heights[i] < heights[idx]) idx = i;
            else if (heights[i] > heights[idx]) break;
        }
        if (idx !== k) { heights[idx]++; continue; }
        // Try right
        for (let i = k+1; i < n; ++i) {
            if (heights[i] < heights[idx]) idx = i;
            else if (heights[i] > heights[idx]) break;
        }
        heights[idx]++;
    }
    return heights;
}