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] <= 100This 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.
C++
Java
Python
C#
JavaScript
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.
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.
C++
Java
Python
C#
JavaScript
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.
| Approach | Complexity |
|---|---|
| Greedy Interval Covering | Time Complexity: O(n), as the algorithm processes the tap ranges in a single pass. |
| Dynamic Programming | Time Complexity: O(n^2), due to the potential iteration across all tap ranges for each garden position. |
LeetCode 1326. Minimum Number of Taps to Open to Water a Garden • Happy Coding • 12,091 views views
Watch 9 more video solutions →Practice Minimum Number of Taps to Open to Water a Garden with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor