Learn AI Create the Future — with Pranay
Main site

LeetCode solutions

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

My accepted Python solution to LeetCode problem 1451, Minimum Number of Taps to Open to Water a Garden, running in 24ms.

  • Difficulty: Hard
  • Python
  • Runtime 24ms
  • Memory 17.9MB

Read the problem on LeetCode View on GitHub

The problem statement is LeetCode’s and stays on their site. What follows is my accepted solution.

Python

Accepted on LeetCode — runtime 24ms, memory 17.9MB, accepted 2025-12-29.

python
class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        # Convert to intervals and find max reach from each position
        max_reach = [0] * (n + 1)
        for i, r in enumerate(ranges):
            left = max(0, i - r)
            right = min(n, i + r)
            max_reach[left] = max(max_reach[left], right)
        
        # Greedy approach similar to Jump Game II
        taps = 0
        curr_end = 0
        next_end = 0
        
        for i in range(n + 1):
            if i > next_end:
                return -1  # Cannot reach position i
            if i > curr_end:
                taps += 1
                curr_end = next_end
            next_end = max(next_end, max_reach[i])
        
        return taps

Source