Skip to content

1326. Minimum Number of Taps to Open to Water a Garden 👍

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
 public:
  int minTaps(int n, vector<int>& ranges) {
    vector<int> nums(n + 1);

    for (int i = 0; i <= n; ++i) {
      int l = max(0, i - ranges[i]);
      int r = min(n, i + ranges[i]);
      nums[l] = max(nums[l], r - l);
    }

    int ans = 0;
    int end = 0;
    int farthest = 0;

    for (int i = 0; i < n; i++) {
      farthest = max(farthest, i + nums[i]);
      if (i == end) {
        ++ans;
        end = farthest;
      }
    }

    return end == n ? ans : -1;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
  public int minTaps(int n, int[] ranges) {
    int[] nums = new int[n + 1];

    for (int i = 0; i <= n; ++i) {
      int l = Math.max(0, i - ranges[i]);
      int r = Math.min(n, i + ranges[i]);
      nums[l] = Math.max(nums[l], r - l);
    }

    int ans = 0;
    int end = 0;
    int farthest = 0;

    for (int i = 0; i < n; i++) {
      farthest = Math.max(farthest, i + nums[i]);
      if (i == end) {
        ++ans;
        end = farthest;
      }
    }

    return end == n ? ans : -1;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
  def minTaps(self, n: int, ranges: list[int]) -> int:
    nums = [0] * (n + 1)

    for i, range_ in enumerate(ranges):
      l = max(0, i - range_)
      r = min(n, range_ + i)
      nums[l] = max(nums[l], r - l)

    ans = 0
    end = 0
    farthest = 0

    for i in range(n):
      farthest = max(farthest, i + nums[i])
      if i == end:
        ans += 1
        end = farthest

    return ans if end == n else -1