Minimum Number of Taps to Open to Water a Garden solution and explanation
Google
9 more videos on this problem
Minimum Number of Taps to Open to Water a Garden | Full Dry Run | ATLASSIAN | Leetcode - 1326codestorywithMIK · 24:34 · 17K views
LeetCode 1326. Minimum Number of Taps to Open to Water a GardenHappy Coding · 9:34 · 12K views
Minimum Number of Taps to Open to Water a Garden | Recursion | Memoization | Leetcode - 1326codestorywithMIK · 26:51 · 8K views
Minimum Number of Taps to Open to Water a Garden I Day 006 | Greedy I Leetcode 1326Aryan Mittal · 32:46 · 8K views
Minimum Number of Taps to Open to Water a Garden: Leetcode 1326Tony Teaches · 17:09 · 5K views
1326. Minimum Number of Taps to Open to Water a Garden | Leetcode Hard | DSA buddy | Easy solutionDSA Buddy · 13:08 · 1K views
Daily Leetcode #1248: Aug 31, 2023 - 1326. Minimum Number of Taps to Open to Water a GardenProgramming Live with Larry · 19:30 · 1K views
Minimum Number of Taps to Open to Water a Garden - LeetCode 1326 - GreedyAlpha-Code · 30:25 · 434 views
1326 || Minimum Number of Taps to Open to Water a Garden || C++ || Leetcode Daily ChallengeCodeFreaks · 14:44 · 344 views
minimum number of taps to open to water a garden leetcode 1326CodeMystique · 7:56 · 162 views
The 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:
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 <= 104ranges.length == n + 10 <= ranges[i] <= 100
Approach overview
Problem Overview: You have a one-dimensional garden from 0 to n. Each tap at position i waters an interval [i - ranges[i], i + ranges[i]]. The task is to open the minimum number of taps so the entire garden is covered. If full coverage is impossible, return -1.
Approach 1: Dynamic Programming (O(n²) time, O(n) space)
Dynamic programming treats the garden like a reachability problem. Create a dp array where dp[i] stores the minimum taps needed to cover the segment [0, i]. For each tap, compute the interval it covers and try updating all reachable positions inside that interval. This means iterating through previous states and relaxing transitions similar to interval DP. The approach is straightforward and helps reason about partial coverage, but the nested updates lead to O(n²) time in the worst case. Useful when building intuition about interval coverage or when greedy reasoning is not immediately obvious.
Approach 2: Greedy Interval Covering (O(n) time, O(n) space)
The optimal solution converts the problem into a classic interval covering task, similar to the Jump Game greedy strategy. First preprocess taps to compute the farthest right boundary reachable from every left boundary. Then iterate from left to right while tracking the current coverage and the farthest extension possible from taps encountered so far. When the iteration reaches the end of the current coverage, you must "open" a new tap by extending to the farthest reachable boundary. This greedy expansion guarantees the minimum number of taps because each step maximizes coverage. The algorithm runs in O(n) time and uses O(n) extra space for preprocessing.
The key insight: always extend the coverage as far as possible before committing to opening another tap. This prevents unnecessary tap activations and mirrors optimal interval scheduling strategies used in many greedy problems.
The preprocessing step relies on scanning the array of ranges and computing coverage boundaries, while the greedy sweep handles the minimal selection logic. An alternative formulation using dynamic programming exists, but it is slower.
Recommended for interviews: The greedy interval covering solution. Interviewers expect candidates to recognize the connection to Jump Game–style greedy expansion. Mentioning the DP formulation first shows you understand the state transition, but implementing the O(n) greedy strategy demonstrates strong algorithmic insight.
Approach 1: Greedy Interval Covering
This approach involves treating each tap as an interval [i-ranges[i], i+ranges[i]], and seeking the minimal number of such intervals required to cover the entire garden range [0, n]. The key is to employ a greedy algorithm which iteratively selects the interval that extends the coverage furthest at each point. Specifically, from each starting point, choose the interval that reaches farthest within the current range, then jump to the furthest point reached by the selected intervals and repeat the process.
class Solution:
def minTaps(self, n: int, ranges: List[int]) -> int:
max_range = [0] * (n + 1)
for i in range(n + 1):
left = max(0, i - ranges[i])
right = min(n, i + ranges[i])
max_range[left] = max(max_range[left], right)
taps = 0
curr_end = 0
next_end = 0
for i in range(n + 1):
if i > next_end:
return -1
if i > curr_end:
taps += 1
curr_end = next_end
next_end = max(next_end, max_range[i])
return taps
# Example usage
sol = Solution()
print(sol.minTaps(5, [3, 4, 1, 1, 0, 0])) # Output: 1import java.util.Arrays;
public class Solution {
public int minTaps(int n, int[] ranges) {
int[] maxRange = new int[n + 1];
Arrays.fill(maxRange, 0);
for (int i = 0; i <= n; i++) {
int left = Math.max(0, i - ranges[i]);
int right = Math.min(n, i + ranges[i]);
maxRange[left] = Math.max(maxRange[left], right);
}
int taps = 0, currEnd = 0, nextEnd = 0;
for (int i = 0; i <= n; i++) {
if (i > nextEnd) return -1;
if (i > currEnd) {
taps++;
currEnd = nextEnd;
}
nextEnd = Math.max(nextEnd, maxRange[i]);
}
return currEnd >= n ? taps : -1;
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] ranges = {3, 4, 1, 1, 0, 0};
int n = 5;
System.out.println(solution.minTaps(n, ranges)); // Output: 1
}
}#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
int minTaps(int n, vector<int>& ranges) {
vector<int> maxRange(n + 1, 0);
for (int i = 0; i <= n; ++i) {
int left = max(0, i - ranges[i]);
int right = min(n, i + ranges[i]);
maxRange[left] = max(maxRange[left], right);
}
int taps = 0, currEnd = 0, nextEnd = 0;
for (int i = 0; i <= n; ++i) {
if (i > nextEnd) return -1;
if (i > currEnd) {
taps++;
currEnd = nextEnd;
}
nextEnd = max(nextEnd, maxRange[i]);
}
return taps;
}
};var minTaps = function(n, ranges) {
let maxRange = new Array(n + 1).fill(0);
for (let i = 0; i <= n; i++) {
let left = Math.max(0, i - ranges[i]);
let right = Math.min(n, i + ranges[i]);
maxRange[left] = Math.max(maxRange[left], right);
}
let taps = 0, currEnd = 0, nextEnd = 0;
for (let i = 0; i <= n; i++) {
if (i > nextEnd) return -1;
if (i > currEnd) {
taps++;
currEnd = nextEnd;
}
nextEnd = Math.max(nextEnd, maxRange[i]);
}
return taps;
};
console.log(minTaps(5, [3, 4, 1, 1, 0, 0])); // Output: 1#include <stdio.h>
#include <string.h>
#include <limits.h>
int minTaps(int n, int* ranges, int rangesSize) {
int maxRange[n + 1];
memset(maxRange, 0, sizeof(maxRange));
for (int i = 0; i <= n; ++i) {
int left = (i - ranges[i] < 0) ? 0 : i - ranges[i];
int right = (i + ranges[i] > n) ? n : i + ranges[i];
maxRange[left] = right > maxRange[left] ? right : maxRange[left];
}
int taps = 0, currEnd = 0, nextEnd = 0;
for (int i = 0; i <= n && currEnd < n; ++i) {
if (i > nextEnd) return -1;
if (i > currEnd) {
taps++;
currEnd = nextEnd;
}
nextEnd = nextEnd > maxRange[i] ? nextEnd : maxRange[i];
}
return currEnd >= n ? taps : -1;
}
int main() {
int ranges[] = {3, 4, 1, 1, 0, 0};
int n = 5;
printf("%d\n", minTaps(n, ranges, 6)); // Output: 1
return 0;
}public class Solution {
public int MinTaps(int n, int[] ranges) {
int[] maxRange = new int[n + 1];
for (int i = 0; i <= n; i++) {
int left = Math.Max(0, i - ranges[i]);
int right = Math.Min(n, i + ranges[i]);
maxRange[left] = Math.Max(maxRange[left], right);
}
int taps = 0, currEnd = 0, nextEnd = 0;
for (int i = 0; i <= n; i++) {
if (i > nextEnd) return -1;
if (i > currEnd) {
taps++;
currEnd = nextEnd;
}
nextEnd = Math.Max(nextEnd, maxRange[i]);
}
return currEnd >= n ? taps : -1;
}
public static void Main(string[] args) {
Solution sol = new Solution();
int[] ranges = {3, 4, 1, 1, 0, 0};
int n = 5;
Console.WriteLine(sol.MinTaps(n, ranges)); // Output: 1
}
}In this Python solution, the aim is to compute the maximum rightward extension possible starting from each point in the garden. The function then proceeds to select minimal and optimal tap combinations that cover the entire garden without leaking.
Time Complexity: O(n), because of a single traversal through all garden points.
Space Complexity: O(n), as it utilizes the max_range list to store ranges.
Approach 2: Dynamic Programming
This approach takes on the problem by formulating it into a dynamic programming challenge. Here, the idea is to maintain an array dp[], where dp[i] denotes the minimum number of taps required to water up to position i. Start by initializing dp[i] with infinity, except dp[0]=0, then update each dp[i] by considering if current tap can extend water coverage from any previous dp positions.
class Solution:
def minTaps(self, n: int, ranges: List[int]) -> int:
dp = [float('inf')] * (n + 1)
dp[0] = 0
for i in range(n + 1):
left, right = max(0, i - ranges[i]), min(n, i + ranges[i])
for j in range(left, right + 1):
dp[j] = min(dp[j], dp[left] + 1)
return dp[n] if dp[n] < float('inf') else -1
# Example usage
sol = Solution()
print(sol.minTaps(5, [3, 4, 1, 1, 0, 0])) # Output: 1import java.util.Arrays;
public class Solution {
public int minTaps(int n, int[] ranges) {
int[] dp = new int[n + 1];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;
for (int i = 0; i <= n; i++) {
int left = Math.max(0, i - ranges[i]);
int right = Math.min(n, i + ranges[i]);
for (int j = left; j <= right; j++) {
if (dp[left] != Integer.MAX_VALUE) {
dp[j] = Math.min(dp[j], dp[left] + 1);
}
}
}
return dp[n] == Integer.MAX_VALUE ? -1 : dp[n];
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] ranges = {3, 4, 1, 1, 0, 0};
int n = 5;
System.out.println(solution.minTaps(n, ranges)); // Output: 1
}
}#include <vector>
#include <limits>
using namespace std;
class Solution {
public:
int minTaps(int n, vector<int>& ranges) {
vector<int> dp(n + 1, INT_MAX);
dp[0] = 0;
for (int i = 0; i <= n; ++i) {
int left = i - ranges[i];
int right = i + ranges[i];
for (int j = max(0, left); j <= min(n, right); ++j) {
if (dp[left] != INT_MAX) {
dp[j] = min(dp[j], dp[left] + 1);
}
}
}
return dp[n] == INT_MAX ? -1 : dp[n];
}
};var minTaps = function(n, ranges) {
let dp = new Array(n + 1).fill(Infinity);
dp[0] = 0;
for (let i = 0; i <= n; i++) {
let left = Math.max(0, i - ranges[i]);
let right = Math.min(n, i + ranges[i]);
for (let j = left; j <= right; j++) {
if (dp[left] != Infinity) {
dp[j] = Math.min(dp[j], dp[left] + 1);
}
}
}
return dp[n] === Infinity ? -1 : dp[n];
};
console.log(minTaps(5, [3, 4, 1, 1, 0, 0])); // Output: 1#include <stdio.h>
#include <limits.h>
#include <string.h>
int minTaps(int n, int* ranges, int rangesSize) {
int dp[n + 1];
for (int i = 0; i <= n; ++i) {
dp[i] = INT_MAX;
}
dp[0] = 0;
for (int i = 0; i <= n; ++i) {
int left = i - ranges[i];
int right = i + ranges[i];
for (int j = (left < 0 ? 0 : left); j <= (right > n ? n : right); ++j) {
if (dp[left] != INT_MAX) {
dp[j] = dp[j] < dp[left] + 1 ? dp[j] : dp[left] + 1;
}
}
}
return dp[n] == INT_MAX ? -1 : dp[n];
}
int main() {
int ranges[] = {3, 4, 1, 1, 0, 0};
int n = 5;
printf("%d\n", minTaps(n, ranges, 6)); // Output: 1
return 0;
}public class Solution {
public int MinTaps(int n, int[] ranges) {
int[] dp = new int[n + 1];
Array.Fill(dp, int.MaxValue);
dp[0] = 0;
for (int i = 0; i <= n; i++) {
int left = Math.Max(0, i - ranges[i]);
int right = Math.Min(n, i + ranges[i]);
for (int j = left; j <= right; j++) {
if (dp[left] != int.MaxValue) {
dp[j] = Math.Min(dp[j], dp[left] + 1);
}
}
}
return dp[n] == int.MaxValue ? -1 : dp[n];
}
public static void Main(string[] args) {
Solution sol = new Solution();
int[] ranges = {3, 4, 1, 1, 0, 0};
int n = 5;
Console.WriteLine(sol.MinTaps(n, ranges)); // Output: 1
}
}The Python solution similarly employs a dp list initialized to infinity, using it to record the fewest taps needed to manage coverage through updating each segment based on the maximum and minimum indices a tap can cover.
Time Complexity: O(n^2), as nested loops tackle each segment coverage possibility.
Space Complexity: O(n), given the dp array's size requirement.
Approach 3: Greedy
We note that for all taps that can cover a certain left endpoint, choosing the tap that can cover the farthest right endpoint is optimal.
Therefore, we can preprocess the array ranges. For the i-th tap, it can cover the left endpoint l = max(0, i - ranges[i]) and the right endpoint r = i + ranges[i]. We calculate the position of the tap that can cover the left endpoint l with the farthest right endpoint and record it in the array last[i].
Then we define the following three variables:
- Variable
ansrepresents the final answer, i.e., the minimum number of taps; - Variable
mxrepresents the farthest right endpoint that can currently be covered; - Variable
prerepresents the farthest right endpoint covered by the previous tap.
We traverse all positions in the range [0, ldots, n-1]. For the current position i, we use last[i] to update mx, i.e., mx = max(mx, last[i]).
- If
mx leq i, it means the next position cannot be covered, so we return-1. - If
pre = i, it means a new subinterval needs to be used, so we incrementansby1and updatepre = mx.
After the traversal, we return ans.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the garden.
Similar problems:
function minTaps(n: number, ranges: number[]): number {
const last = new Array(n + 1).fill(0);
for (let i = 0; i < n + 1; ++i) {
const l = Math.max(0, i - ranges[i]);
const r = i + ranges[i];
last[l] = Math.max(last[l], r);
}
let ans = 0;
let mx = 0;
let pre = 0;
for (let i = 0; i < n; ++i) {
mx = Math.max(mx, last[i]);
if (mx <= i) {
return -1;
}
if (pre == i) {
++ans;
pre = mx;
}
}
return ans;
}func minTaps(n int, ranges []int) (ans int) {
last := make([]int, n+1)
for i, x := range ranges {
l, r := max(0, i-x), i+x
last[l] = max(last[l], r)
}
var pre, mx int
for i, j := range last[:n] {
mx = max(mx, j)
if mx <= i {
return -1
}
if pre == i {
ans++
pre = mx
}
}
return
}impl Solution {
#[allow(dead_code)]
pub fn min_taps(n: i32, ranges: Vec<i32>) -> i32 {
let mut last = vec![0; (n + 1) as usize];
let mut ans = 0;
let mut mx = 0;
let mut pre = 0;
// Initialize the last vector
for (i, &r) in ranges.iter().enumerate() {
if (i as i32) - r >= 0 {
last[((i as i32) - r) as usize] =
std::cmp::max(last[((i as i32) - r) as usize], (i as i32) + r);
} else {
last[0] = std::cmp::max(last[0], (i as i32) + r);
}
}
for i in 0..n as usize {
mx = std::cmp::max(mx, last[i]);
if mx <= (i as i32) {
return -1;
}
if pre == (i as i32) {
ans += 1;
pre = mx;
}
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Greedy Interval Covering | Time Complexity: O(n), because of a single traversal through all garden points. |
| Dynamic Programming | Time Complexity: O(n^2), as nested loops tackle each segment coverage possibility. |
| Greedy | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming | O(n²) | O(n) | When exploring state transitions or building intuition about interval coverage |
| Greedy Interval Covering | O(n) | O(n) | Optimal solution for large inputs and typical interview expectations |
Frequently asked questions
Is Minimum Number of Taps to Open to Water a Garden easy or hard?
LeetCode classifies this problem as Hard because recognizing the greedy interval covering transformation is not immediately obvious. Once mapped to a Jump Game style greedy sweep, the implementation becomes relatively straightforward with O(n) complexity.
Minimum Number of Taps to Open to Water a Garden Python/Java solution
Both Python and Java implementations follow the same greedy logic. First compute the maximum reach for each left boundary, then iterate across the garden while extending the coverage window. Each time the iteration reaches the end of the current range, increment the tap count and expand to the farthest reachable position.
How to solve Minimum Number of Taps to Open to Water a Garden in O(n)?
Preprocess the ranges array so that each index stores the farthest right boundary reachable from that starting point. Then iterate from 0 to n while maintaining the current coverage and the farthest possible extension. When the index reaches the end of the current coverage, open a new tap by extending to the farthest reachable boundary. This greedy expansion guarantees minimal taps in O(n) time.
What is the best approach for Minimum Number of Taps to Open to Water a Garden?
The greedy interval covering approach is the most efficient solution. Convert each tap into an interval and track the farthest reachable point from every starting position. Then perform a greedy sweep similar to the Jump Game strategy, extending coverage whenever the current boundary is reached. This solution runs in O(n) time and uses O(n) preprocessing space.
Is Minimum Number of Taps to Open to Water a Garden asked at Google/Amazon/Meta?
Interval coverage and greedy selection problems similar to this appear in interviews at companies like Google, Amazon, and Meta. The problem tests recognition of interval merging and Jump Game style greedy strategies, which are common patterns in algorithm interviews.
What data structure is used in Minimum Number of Taps to Open to Water a Garden?
The solution primarily uses arrays to store the farthest reachable coverage for each position. The greedy algorithm then scans the array while tracking current and maximum reachable boundaries, similar to techniques used in array-based greedy problems.
What is the time complexity of Minimum Number of Taps to Open to Water a Garden?
The optimal greedy solution runs in O(n) time with O(n) space for preprocessing coverage ranges. A dynamic programming approach also exists but typically runs in O(n^2) time with O(n) space because it updates reachable garden segments for each tap.