# Minimum Number of Taps to Open to Water a Garden LeetCode Solution

Difficulty Level Hard
Razorpay TuSimpleViews 1747

## Problem Statement

Minimum Number of Taps to Open to Water a Garden LeetCode Solution – 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

### Input:

n = 5

ranges = [3, 4, 1, 1, 0, 0] ## 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]

## Approach:

First, eliminate all zero since they are useless. Then sort the array base on the first index, then the second index. After that, we get the first tap by using the 1st loop. With the first tap, we try to find the next tap with the farthest endpoint. The next tap should overlap with the pre-tap. After we find the next tap, update the previous tap.

So, the question is basically asking for the minimum taps, that can cover the whole garden.
Algorithm:

1. `dp[i]` is the minimum number of taps to water `[0, i]`.
Initialize `dp[i]` with max = `n + 2`
`dp = ` as we need no tap to water nothing.
2. Find the leftmost point of the garden to water with a tap `i`.
3. Find the rightmost point of the garden to water with a tap `i`.
4. We can water `[left, right]` with one tap,
and water `[0, left - 1]` with `dp[left - 1]` taps.

## Code for Minimum Number of Taps to Open to Water a Garden

### Java Program

```class Solution {
public int minTaps(int n, int[] A) {
int[] dp = new int[n + 1];
Arrays.fill(dp, n + 2);
dp = 0;
for (int i = 0; i <= n; ++i)
for (int j = Math.max(i - A[i] + 1, 0); j <= Math.min(i + A[i], n); ++j)
dp[j] = Math.min(dp[j], dp[Math.max(0, i - A[i])] + 1);
return dp[n]  < n + 2 ? dp[n] : -1;
}
}```

### C++ Program

```class Solution {
public:
int minTaps(int n, vector<int>& A) {
vector<int> dp(n + 1, n + 2);
dp = 0;
for (int i = 0; i <= n; ++i)
for (int j = max(i - A[i] + 1, 0); j <= min(i + A[i], n); ++j)
dp[j] = min(dp[j], dp[max(0, i - A[i])] + 1);
return dp[n]  < n + 2 ? dp[n] : -1;
}
};```

## Complexity Analysis for Minimum Number of Taps to Open to Water a Garden LeetCode Solution

Time Complexity: `O(NR)`, where `R = ranges[i] <= 100`
Space Complexity: `O(N)`

Translate »