#1326

Hard

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Minimum Number of Taps to Open to Water a Garden

Determine the minimum number of taps to water an entire garden using state transition dynamic programming and interval coverage logic.

array dynamic programming greedy

Problem Statement

You are given a one-dimensional garden that spans from point 0 to point n along the x-axis. There are n + 1 taps at positions 0 through n, each with a defined watering range. Activating a tap at position i covers the interval from max(0, i - ranges[i]) to min(n, i + ranges[i]).

The task is to determine the minimum number of taps that must be opened to water the entire garden from 0 to n. If it is impossible to cover the entire garden, return -1. You are given an integer n and an array ranges of length n + 1 representing the watering range of each tap.

Examples

Example 1

Input: n = 5, ranges = [3,4,1,1,0,0]

Output: 1

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

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

Solution Approach

Convert Tap Ranges to Intervals

For each tap i, compute the effective interval it can water as [max(0, i - ranges[i]), min(n, i + ranges[i])]. Sorting these intervals by their left endpoint simplifies subsequent coverage analysis, which is critical for both greedy and DP approaches.

Greedy Interval Selection

Iterate from the start of the garden, always picking the tap interval that extends coverage the farthest. This ensures minimal taps are selected at each step, aligning with the state transition dynamic programming principle of maximizing coverage efficiently.

Dynamic Programming for State Transitions

Use a DP array where dp[i] represents the minimum taps needed to cover up to point i. Update dp[end] = min(dp[end], dp[start] + 1) for each interval [start, end]. This handles overlapping intervals and guarantees an optimal solution that respects the state transition pattern.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n + k) where n is garden length and k is number of intervals after conversion, dominated by sorting and DP updates. Space complexity is O(n) for the DP array to track minimum taps for each point.

What Interviewers Usually Probe

The problem tests your ability to model ranges as intervals and optimize coverage efficiently.
Expect follow-up questions about greedy versus dynamic programming trade-offs in state transitions.
Watch for edge cases with zero ranges or fully overlapping taps.

Common Pitfalls or Variants

Common pitfalls

Failing to cap intervals within [0, n], leading to index errors.
Not handling intervals that do not fully connect, producing incorrect -1 results.
Ignoring overlapping ranges which may cause suboptimal tap selections if not using DP.

Follow-up variants

Find the maximum garden length that can be watered with a fixed number of taps using similar interval logic.
Calculate minimum taps needed if taps can only be activated consecutively, introducing extra DP constraints.
Consider varying water pressure limits, effectively changing range intervals dynamically during DP updates.

FAQ

What is the core pattern for solving Minimum Number of Taps to Open to Water a Garden?

The key pattern is state transition dynamic programming applied to interval coverage, often combined with a greedy selection for efficiency.

How do I handle taps with zero range in this problem?

Taps with zero range do not contribute coverage, so your DP and greedy interval selection must skip them to avoid false coverage assumptions.

Is sorting intervals necessary for the optimal solution?

Yes, sorting intervals by their left endpoint allows the greedy selection to extend coverage correctly and ensures DP updates are efficient.

Can this problem be solved purely with a greedy approach?

In some cases, greedy alone works, but for overlapping or partially disconnected intervals, DP ensures minimal taps, handling complex state transitions.

What should I do if the garden cannot be fully watered?

Return -1. This occurs when intervals do not fully cover the garden, a common failure mode that GhostInterview flags during analysis.

terminal

Solution

Solution 1: 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.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

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

Continue Practicing

#1363 largest multiple of three #1388 pizza with 3n slices #1262 greatest sum divisible by three