# Minimum Number of Taps to Open to Water a Garden
**Difficulty:** HARD
[External](https://leetcode.com/problems/minimum-number-of-taps-to-open-to-water-a-garden)
Canonical: https://scaleengineer.com/dsa/problems/minimum-number-of-taps-to-open-to-water-a-garden
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** Array
**Companies:** [BNY Mellon](https://scaleengineer.com/companies/bny-mellon), [Flipkart](https://scaleengineer.com/companies/flipkart), [Intuit](https://scaleengineer.com/companies/intuit), [ServiceNow](https://scaleengineer.com/companies/servicenow), [DE Shaw](https://scaleengineer.com/companies/de-shaw), [Akuna Capital](https://scaleengineer.com/companies/akuna-capital)
---
## Problem
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:**

![](https://assets.glich.co/dsa/minimum-number-of-taps-to-open-to-water-a-garden/image0.png) 

**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`

# Approaches
## Naive Greedy Approach
This approach employs a straightforward greedy strategy. At each step, we aim to extend the watered portion of the garden as far as possible. We begin with the assumption that point 0 is our starting line. We then select a tap that can water point 0 (or any point already watered) and extends the furthest to the right. This process is repeated, with each new tap selection pushing the boundary of the watered area, until the entire garden from `[0, n]` is covered.
**Time:** O(T * n), where `T` is the final number of taps and `n` is the length of the garden. In the worst-case scenario, `T` can be proportional to `n`, leading to a time complexity of O(n^2). · **Space:** O(1) extra space, as we are only using a few variables to keep track of the state.
**Pros:** The logic is intuitive and relatively easy to understand.
**Cons:** The time complexity of O(n^2) can be too slow and may result in a 'Time Limit Exceeded' error for large values of `n`.
### Explanation
We maintain a variable, `current_end`, which tracks the rightmost boundary of the watered garden, initially set to 0. We also count the number of `taps` used. The main logic resides in a loop that runs as long as `current_end` is less than `n`. In each iteration of this loop, we simulate opening one more tap. To make the best choice, we scan through all `n + 1` taps. For each tap, we determine its watering range `[start, end]`. If a tap can begin its watering at or before our `current_end` (`start <= current_end`), it's a candidate for our next choice. We find the candidate tap that offers the maximum possible new `end` point. This maximum `end` becomes our new `current_end`. If, after checking all taps, we find that we cannot extend our `current_end` at all, it signifies that we're stuck and can't water the rest of the garden, so we return -1. Otherwise, we continue this process until `current_end` reaches or surpasses `n`.

```java
class Solution {
    public int minTaps(int n, int[] ranges) {
        int taps = 0;
        int current_end = 0;

        while (current_end < n) {
            taps++;
            int max_reach = current_end;
            for (int i = 0; i < ranges.length; i++) {
                int start = Math.max(0, i - ranges[i]);
                int end = Math.min(n, i + ranges[i]);
                if (start <= current_end) {
                    max_reach = Math.max(max_reach, end);
                }
            }

            if (max_reach == current_end) {
                return -1; // Cannot extend coverage
            }
            current_end = max_reach;
        }

        return taps;
    }
}
```
### Algorithm
1. Initialize `taps = 0` and `current_end = 0`. `current_end` represents the farthest point of the garden that is currently watered.
2. Start a loop that continues as long as the entire garden is not watered (`current_end < n`).
3. Inside the loop, we decide to use one more tap, so increment `taps`.
4. Find the best possible next tap. Initialize a variable `max_reach = current_end`.
5. Iterate through all available taps from `i = 0` to `n`. For each tap, calculate its watering interval `[start, end]`.
6. If a tap's interval starts at or before the currently watered point (`start <= current_end`), it can be used to extend the coverage. Update `max_reach = max(max_reach, end)`.
7. After checking all taps, if `max_reach` has not increased (i.e., `max_reach == current_end`), it's impossible to extend the coverage further. This means the garden cannot be fully watered, so return -1.
8. Otherwise, update `current_end = max_reach` to reflect the new watered area.
9. If the loop finishes, it means `current_end >= n`, and the entire garden is watered. Return the total `taps` used.

## Greedy Approach with Sorting
This approach refines the naive greedy strategy by pre-processing the tap ranges. Instead of repeatedly scanning all taps, we first convert them into intervals and sort these intervals by their starting points. This allows for a more efficient single pass to find the optimal next tap at each step. The core greedy choice remains the same: from the currently watered area, pick a tap that reaches the farthest.
**Time:** O(n log n), dominated by the sorting of intervals. The subsequent greedy selection loop runs in O(n) time because we iterate through the intervals with a single pass. · **Space:** O(n) to store the list of intervals.
**Pros:** Significantly more efficient than the naive O(n^2) approach.; It's a standard and robust pattern for solving interval-based covering problems.
**Cons:** The sorting step has a time complexity of O(n log n), which is the bottleneck for this approach.
### Explanation
The first step is to represent each tap as an interval `[start, end]`. We create a list of these intervals. Then, we sort this list based on the `start` values. This sorting is key, as it allows us to consider taps in the order of their starting positions.

We then proceed with the greedy selection. We use `current_end` to track our progress. In each step, we need to select a new tap. We look at all the intervals that can be 'activated' from our current position (i.e., their `start` is less than or equal to `current_end`). Thanks to the sorting, these intervals will be contiguous in our list. We iterate through them, find the one that provides the maximum `end`, and set that as our `next_end`. We then update `current_end` to this `next_end` and increment our tap count. A single pointer `i` is used to traverse the sorted interval list, ensuring we don't re-evaluate intervals unnecessarily.

```java
import java.util.Arrays;
import java.util.Comparator;

class Solution {
    public int minTaps(int n, int[] ranges) {
        int[][] intervals = new int[n + 1][2];
        for (int i = 0; i <= n; i++) {
            intervals[i][0] = Math.max(0, i - ranges[i]);
            intervals[i][1] = Math.min(n, i + ranges[i]);
        }

        Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));

        int taps = 0;
        int current_end = 0;
        int next_end = 0;
        int i = 0;

        while (current_end < n) {
            taps++;
            while (i <= n && intervals[i][0] <= current_end) {
                next_end = Math.max(next_end, intervals[i][1]);
                i++;
            }

            if (next_end <= current_end) {
                return -1; // Cannot make progress
            }
            current_end = next_end;
        }

        return taps;
    }
}
```
### Algorithm
1. First, transform the `ranges` array into a list of intervals. For each tap `i`, create an interval `[start, end]` where `start = max(0, i - ranges[i])` and `end = min(n, i + ranges[i])`.
2. Sort this list of intervals based on their `start` points in ascending order.
3. Initialize `taps = 0`, `current_end = 0`, `next_end = 0`, and an interval pointer `i = 0`.
4. Begin a loop that continues as long as `current_end < n`.
5. In each iteration, representing the selection of one tap, increment `taps`.
6. Use a nested loop to iterate through the sorted intervals (starting from index `i`) as long as their start point is within the currently watered range (`intervals[i].start <= current_end`). For each such interval, update `next_end` to be the maximum end point seen so far (`next_end = max(next_end, intervals[i].end)`).
7. After the inner loop, if `next_end` has not advanced beyond `current_end`, it's impossible to proceed. Return -1.
8. Update `current_end = next_end`.
9. If the main loop completes, return `taps`.

## Optimized Linear Time Greedy Approach
This approach is the most optimal, achieving a linear time solution. It cleverly avoids the O(n log n) sorting step by using an auxiliary array. The problem is reframed into a variant of the 'Jump Game II' problem. We first precompute the maximum reach from every possible starting point in the garden. Then, we use a greedy algorithm to make the minimum number of 'jumps' (i.e., open the minimum number of taps) to cover the garden from 0 to `n`.
**Time:** O(n). The precomputation step to build the `max_reach` array is O(n), and the final greedy pass is also O(n). · **Space:** O(n) for the auxiliary `max_reach` array.
**Pros:** Achieves the best possible time complexity of O(n).; Highly efficient for large inputs.
**Cons:** The logic can be slightly less intuitive as it transforms the problem into another known pattern ('Jump Game').
### Explanation
The key insight is to efficiently find the maximum reach from any given point. We create an array `max_reach` of size `n + 1`. We process the `ranges` array once: for each tap `i`, it defines an interval `[start, end]`. We use this to update our `max_reach` array such that `max_reach[start]` stores the maximum possible `end` for any tap starting at `start`. This precomputation takes O(n) time.

With the `max_reach` array, the problem becomes: starting at index 0, at each position `i`, you can 'jump' to any position up to `max_reach[i]`. What is the minimum number of jumps to reach or exceed `n`? This can be solved greedily in a single pass. We keep track of `current_end` (the farthest we can get with the current taps) and `next_end` (the farthest we can get with one more tap). As we iterate through the garden points `i`, we update `next_end`. When `i` reaches `current_end`, it's time to 'jump' – we increment our tap count and set `current_end` to the new `next_end` we found.

```java
class Solution {
    public int minTaps(int n, int[] ranges) {
        int[] max_reach = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            int start = Math.max(0, i - ranges[i]);
            int end = Math.min(n, i + ranges[i]);
            max_reach[start] = Math.max(max_reach[start], end);
        }

        int taps = 0;
        int current_end = 0;
        int next_end = 0;

        for (int i = 0; i < n; i++) {
            if (i > next_end) { // Current position is unreachable
                return -1;
            }
            next_end = Math.max(next_end, max_reach[i]);
            if (i == current_end) { // Must use a new tap
                taps++;
                current_end = next_end;
            }
        }
        
        // If current_end can't reach n, it's impossible
        return current_end >= n ? taps : -1;
    }
}
```
### Algorithm
1. Create an auxiliary array `max_reach` of size `n + 1`, initialized to all zeros.
2. Iterate through the taps from `i = 0` to `n`. For each tap, calculate its range `[start, end]`.
3. For each tap, update `max_reach[start] = max(max_reach[start], end)`. After this loop, `max_reach[i]` will store the farthest point reachable from any tap whose range starts at `i`.
4. Now, solve the problem using a greedy approach similar to the 'Jump Game II' problem.
5. Initialize `taps = 0`, `current_end = 0` (farthest reach with `taps` taps), and `next_end = 0` (farthest reach with `taps + 1` taps).
6. Iterate through the garden from `i = 0` to `n - 1`.
7. In each iteration, update the potential next reach: `next_end = max(next_end, max_reach[i])`.
8. If the current position `i` is the boundary of our current reach (`i == current_end`), it means we must use a tap. We increment `taps` and update `current_end` to `next_end`.
9. If `current_end` ever becomes greater than or equal to `n`, we have successfully covered the garden, and we can stop and return the tap count.
10. If the loop finishes and `current_end < n`, it's impossible to cover the garden, so return -1.

# Solutions
### Java

```java
class Solution {
public
  int minTaps(int n, int[] ranges) {
    int[] last = new int[n + 1];
    for (int i = 0; i < n + 1; ++i) {
      int l = Math.max(0, i - ranges[i]), r = i + ranges[i];
      last[l] = Math.max(last[l], r);
    }
    int ans = 0, mx = 0, pre = 0;
    for (int i = 0; i < n; ++i) {
      mx = Math.max(mx, last[i]);
      if (mx <= i) {
        return -1;
      }
      if (pre == i) {
        ++ans;
        pre = mx;
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minTaps(int n, vector<int> &ranges) {
    vector<int> last(n + 1);
    for (int i = 0; i < n + 1; ++i) {
      int l = max(0, i - ranges[i]), r = i + ranges[i];
      last[l] = max(last[l], r);
    }
    int ans = 0, mx = 0, pre = 0;
    for (int i = 0; i < n; ++i) {
      mx = max(mx, last[i]);
      if (mx <= i) {
        return -1;
      }
      if (pre == i) {
        ++ans;
        pre = mx;
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int: last = [0] * (n + 1) for i, x in enumerate(ranges): l, r = max(0, i - x), i + x last[l] = max(last[l], r) ans = mx = pre = 0 for i in range(n): mx = max(mx, last[i]) if mx <= i: return - 1 if pre == i: ans += 1 pre = mx return ans

```