Pour water

Array Simulation

48.6% acceptance

Mar 31, 2026

314

813

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.

Solution

Rust

Time O(n²)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn pour_water(heights: Vec<i32>, volume: i32, k: i32) -> Vec<i32> {
    let mut heights = heights;
    let k = k as usize;
    let n = heights.len();
    for _ in 0..volume {
      let mut pos = k;
      // Scan left as far as possible
      while pos > 0 && heights[pos - 1] <= heights[pos] {
        pos -= 1;
      }
      // Flow back right to local minimum
      while pos < k && heights[pos + 1] <= heights[pos] {
        pos += 1;
      }
      if pos == k {
        // No left fall; try right
        while pos < n - 1 && heights[pos + 1] <= heights[pos] {
          pos += 1;
        }
        // Flow back left to local minimum
        while pos > k && heights[pos - 1] <= heights[pos] {
          pos -= 1;
        }
      }
      heights[pos] += 1;
    }
    heights
  }
}