Pour Water

medium simulation arrays greedy

Problem

Given heights of terrain and an index k where water drops fall, simulate V drops. Each drop tries to flow left to the lowest position, otherwise right to the lowest position, otherwise rests at k. Return the resulting heights.

Inputheights=[2,1,1,2,1,2,2], V=4, K=3

Output[2,2,2,3,2,2,2]

Four units of water poured at index 3 settle as shown.

input

def pourWater(heights, V, K):
    for _ in range(V):
        placed = False
        for d in (-1, 1):
            i, j = K, K
            while 0 <= i+d < len(heights) and heights[i+d] <= heights[i]:
                if heights[i+d] < heights[i]:
                    j = i+d
                i += d
            if j != K:
                heights[j] += 1
                placed = True
                break
        if not placed:
            heights[K] += 1
    return heights

function pourWater(heights, V, K) {
  for (let v = 0; v < V; v++) {
    let placed = false;
    for (const d of [-1, 1]) {
      let i = K, j = K;
      while (i+d >= 0 && i+d < heights.length && heights[i+d] <= heights[i]) {
        if (heights[i+d] < heights[i]) j = i+d;
        i += d;
      }
      if (j !== K) { heights[j]++; placed = true; break; }
    }
    if (!placed) heights[K]++;
  }
  return heights;
}

int[] pourWater(int[] heights, int V, int K) {
    for (int v = 0; v < V; v++) {
        boolean placed = false;
        for (int d : new int[]{-1, 1}) {
            int i = K, j = K;
            while (i+d >= 0 && i+d < heights.length && heights[i+d] <= heights[i]) {
                if (heights[i+d] < heights[i]) j = i+d;
                i += d;
            }
            if (j != K) { heights[j]++; placed = true; break; }
        }
        if (!placed) heights[K]++;
    }
    return heights;
}

vector<int> pourWater(vector<int>& heights, int V, int K) {
    for (int v = 0; v < V; v++) {
        bool placed = false;
        for (int d : {-1, 1}) {
            int i = K, j = K;
            while (i+d >= 0 && i+d < (int)heights.size() && heights[i+d] <= heights[i]) {
                if (heights[i+d] < heights[i]) j = i+d;
                i += d;
            }
            if (j != K) { heights[j]++; placed = true; break; }
        }
        if (!placed) heights[K]++;
    }
    return heights;
}

Explanation

This is a simulation: we drop water one unit at a time and follow the rule that water always rolls to the lowest reachable spot, trying left first, then right, and resting in place if neither helps.

For each of the V drops, we try both directions d = -1 (left) and d = 1 (right). Walking that way from K, we can only keep moving while the next cell is not higher than where we stand (heights[i+d] <= heights[i]), and we remember the index j of the lowest dip we pass.

If the left scan found a genuinely lower spot (j != K), the drop settles there and we stop; otherwise we try the right scan the same way. The left-first order is what makes ties resolve toward the left, as the problem requires.

If neither side has a lower landing, the water just rests at K and that column rises by one.

Example: with heights = [2,1,1,2,1,2,2], K = 3, the first drop rolls left into the dip and fills it; after all 4 drops the terrain becomes [2,2,2,3,2,2,2].

Time: O(V*n) Space: O(1)