Minimum Number of Taps to Open to Water a Garden - Solution & Explanation

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

HardArray Dynamic Programming Greedy25 min readAsked at: Amazon, Microsoft, Meta +10

Practice this problem

Problem Statement

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 <= 10⁴
ranges.length == n + 1
0 <= 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.

This C solution first transforms the ranges into maximum right reach for each start position. It employs a greedy approach, moving through the garden while extending the reach of water as far as possible with the least number of taps activated. If a gap or unwatered region is found, it returns -1.

Code

C C++Java Python C#JavaScript

C++

Java

Python

JavaScript

Complexity

Time Complexity: O(n), as the algorithm processes the tap ranges in a single pass.
Space Complexity: O(n), due to the storage for the maxRange array.

Try this approach in the editor →

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.

This C implementation establishes an array, dp[], with each index representing the minimal taps needed to reach that point. By updating the array through possible coverage ranges of each tap, it identifies the least number capable to span the whole garden.

Code

C C++Java Python C#JavaScript

C++

Java

Python

JavaScript

Complexity

Time Complexity: O(n^2), due to the potential iteration across all tap ranges for each garden position.
Space Complexity: O(n), as a dp array of size n+1 is maintained.

Try this approach in the editor →

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 ans represents the final answer, i.e., the minimum number of taps;
Variable mx represents the farthest right endpoint that can currently be covered;
Variable pre represents 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 increment ans by 1 and update pre = 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.

Code

Python Java C++Go TypeScript Rust

Python

Java

C++

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

Approach	Complexity
Greedy Interval Covering	Time Complexity: O(n), as the algorithm processes the tap ranges in a single pass. Space Complexity: O(n), due to the storage for the maxRange array.
Dynamic Programming	Time Complexity: O(n^2), due to the potential iteration across all tap ranges for each garden position. Space Complexity: O(n), as a dp array of size n+1 is maintained.
Greedy	—

Detailed 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

Video Solution

Minimum Number of Taps to Open to Water a Garden | Full Dry Run | ATLASSIAN | Leetcode - 1326 • codestorywithMIK • 17,116 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Minimum Number of Taps to Open to Water a Garden with our built-in code editor and test cases.

Practice on FleetCode

Two Sum

Median of Two Sorted Arrays

Problem Info

DifficultyHard

Acceptance50.7%

Approaches3

Reading time25 min

Asked at

Amazon Microsoft Meta Morgan Stanley Salesforce

Practice this problem

Open in Editor

Problem Statement

Approach Overview

Approach 1: Greedy Interval Covering

Code

Complexity

Approach 2: Dynamic Programming

Code

Complexity

Approach 3: Greedy

Code

Complexity Comparison

Detailed Complexity Analysis

Video Solution

Frequently Asked Questions

Related Problems

Ready to solve this problem?

Problem Info

Table of Contents