1326. Minimum Number of Taps to Open to Water a Garden LeetCode Solution

In this guide, you will get 1326. Minimum Number of Taps to Open to Water a Garden LeetCode Solution with the best time and space complexity. The solution to Minimum Number of Taps to Open to Water a Garden problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Minimum Number of Taps to Open to Water a Garden solution in C++
Minimum Number of Taps to Open to Water a Garden solution in Java
Minimum Number of Taps to Open to Water a Garden solution in Python
Additional Resources

1326. Minimum Number of Taps to Open to Water a Garden LeetCode Solution image

Problem Statement of Minimum Number of Taps to Open to Water a Garden

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.

Example 1:

Input: n = 5, ranges = [3,4,1,1,0,0]
Output: 1
Explanation: The tap at point 0 can cover the interval [-3,3]
The tap at point 1 can cover the interval [-3,5]
The tap at point 2 can cover the interval [1,3]
The tap at point 3 can cover the interval [2,4]
The tap at point 4 can cover the interval [4,4]
The tap at point 5 can cover the interval [5,5]
Opening Only the second tap will water the whole garden [0,5]

Example 2:

Input: n = 3, ranges = [0,0,0,0]
Output: -1
Explanation: Even if you activate all the four taps you cannot water the whole garden.

Constraints:

1 <= n <= 104
ranges.length == n + 1
0 <= ranges[i] <= 100

Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(n)

1326. Minimum Number of Taps to Open to Water a Garden LeetCode Solution in C++

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;
  }
};
/* code provided by PROGIEZ */

1326. Minimum Number of Taps to Open to Water a Garden LeetCode Solution in Java

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;
  }
}
// code provided by PROGIEZ

1326. Minimum Number of Taps to Open to Water a Garden LeetCode Solution in Python

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
 # code by PROGIEZ