Minimum number of taps to open to water a garden

Array Dynamic Programming Greedy

51.0% acceptance

Feb 25, 2026

3617

197

There is a one-dimensional garden on the x-axis. The garden starts at the point 0 and ends at the point n. (i.e., the length of the garden is n). There are n + 1 taps located at points [0, 1, ..., n] in the garden. Given an integer n and an integer array ranges of length n + 1 where ranges[i] (0-indexed) means the i-th tap can water the area [i - ranges[i], i + ranges[i]] if it was open. Return the minimum number of taps that should be open to water the whole garden, If the garden cannot be watered return -1.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn min_taps(n: i32, ranges: Vec<i32>) -> i32 {
    let n = n as usize;
    // Convert to interval covering problem
    // For each tap i with range r, it covers [max(0, i-r), min(n, i+r)]
    // We need to cover [0, n] with minimum intervals
    // Use greedy: for each start position, track max reachable end
    let mut max_reach = vec![0usize; n + 1];
    for i in 0..=n {
      let r = ranges[i] as usize;
      let left = if i >= r { i - r } else { 0 };
      let right = (i + r).min(n);
      if right > max_reach[left] {
        max_reach[left] = right;
      }
    }
    // Greedy jump game: like jump game II
    let mut taps = 0;
    let mut cur_end = 0;
    let mut far = 0;
    for i in 0..n {
      far = far.max(max_reach[i]);
      if i == cur_end {
        if far == cur_end { return -1; }
        taps += 1;
        cur_end = far;
        if cur_end >= n { break; }
      }
    }
    if cur_end >= n { taps } else { -1 }
  }
}