Space

Open

From Fieldwork

Scales

1326. Minimum Number of Taps to Open to Water a Garden

leetcodegreedyarraydynamic-programminghard

Open pinned source

v1

We will split the problem into two explicit, easy-to-read phases:

Pre-processing: Flatten the confusing "radius" logic into a simple list of "Start to End" intervals.

Simulation: Use a while loop to simulate the process of "standing" at our current limit and looking for the best tap to extend our reach.

Phase 1: Flattening the Map
The input gives us taps with a center and a radius. This is messy to think about. We really just care about: "If I start watering at point X, how far right can I go?"

We can build a simple array max_reach where the index is the start point of the water, and the value is the end point.

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

Tap at index 0 (range 3) covers [-3, 3] -> clipped to [0, 3]

Tap at index 1 (range 4) covers [-3, 5] -> clipped to [0, 5]

We transform this into:

At start point 0, the best reach is index 5.

Phase 2: The Simulation Loop
Instead of a confusing for loop with hidden state changes, let's use a while loop that reads like English:

State: We currently have water up to current_end.

Action: Look at all the intervals that start within our current watered area.

Decision: Pick the one that extends the furthest to the right.

Update: Set current_end to that new furthest point and increment the tap count.

This is better because:
There's no magic i == current_end: The state update happens explicitly at the end of the while block (current_end = next_end). You can see exactly when we decide to add a tap.

Separate Scanning Logic: The inner while loop makes it obvious that we are "scanning" the available options within our current reach.

Gap Detection: The condition if next_end == current_end clearly signifies "we checked all options and couldn't move forward," which means the garden is impossible to water.

This solution is still O(N) time complexity (since index_to_check only moves from 0 to n once), but it prioritizes readability over code golf.

class Solution:
    def minTaps(self, n: int, ranges: list[int]) -> int:
        # --- PHASE 1: Pre-process Taps into Intervals ---
        # max_reach[i] means: "If a tap starts covering at index 'i', 
        # what is the furthest index it reaches?"
        max_reach = [0] * (n + 1)
        
        for i, r in enumerate(ranges):
            # Convert (center, radius) to (start, end)
            start = max(0, i - r)
            end = min(n, i + r)
            
            # We only care about the tap that reaches the furthest from this start point
            max_reach[start] = max(max_reach[start], end)

        # --- PHASE 2: Simulation (Stitching) ---
        taps = 0
        current_end = 0
        next_end = 0
        index_to_check = 0
        
        # While we haven't watered the whole garden
        while current_end < n:
            
            # Scan all possible intervals that start within our current watered range
            # to find the one that pushes 'next_end' the furthest.
            while index_to_check <= current_end:
                next_end = max(next_end, max_reach[index_to_check])
                index_to_check += 1
                
            # If we couldn't find ANY tap to extend our reach, we are stuck.
            # This implies a gap in coverage.
            if next_end == current_end:
                return -1
            
            # We found the best tap. "Turn it on."
            # Our watered area now extends to 'next_end'.
            current_end = next_end
            taps += 1
            
        return taps

v2

See Jump Game.

from typing import List

class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        # Array to store the furthest point reachable from each index.
        # max_reach[i] = max end point for an interval starting at i
        max_reach = [0] * (n + 1)

        # 1. Preprocessing: Convert tap ranges into "jumps"
        for i, r in enumerate(ranges):
            # Calculate the effective bounds of the tap
            start = max(0, i - r)
            end = min(n, i + r)
            
            # We want to know: "If I start at `start`, how far can I go?"
            max_reach[start] = max(max_reach[start], end)

        # 2. Greedy Iteration (Jump Game II logic)
        taps = 0
        current_end = 0
        next_end = 0

        # We iterate up to n-1 because if we reach n, the garden is fully watered.
        for i in range(n):
            # Update the furthest we can reach from current position i
            next_end = max(next_end, max_reach[i])
            
            # If we reach the end of the currently active tap's range:
            if i == current_end:
                # If we cannot move further than current_end, there is a gap.
                if next_end <= i:
                    return -1
                
                # "Jump" to the new furthest reach
                current_end = next_end
                taps += 1
                
                # Optimization: Early exit if we have already covered the whole garden
                if current_end >= n:
                    return taps
                    
        return taps

Practice bench

Continue the thread

A private scratchpad for this reading. Nothing is sent or scored.

You

What is still unclear, or what would change the explanation?

Saved on this device · one draft per mode

leetcodeDec 15, 2025