Minimum Number Of Taps To Open To Water A Garden - Leetcode Solution

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 in different positions in the garden.

You are 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.

Approach:

The approach to solve the problem is to find out the minimum number of intervals required to cover the entire garden.

We can make an assumption in this problem, as the garden needs to water all elements, each tap will water up to the rightmost point it has the range for i.e tap i will water until i+ranges[i].

We can define an array coverage which will mark the endpoints as 1, where this tap has range, for every tap, for example, we visit the first tap, if it has range of 3, we will mark coverage[0]update coverage[0]=1 coverage[1]=1 coverage[2]=1 coverage[3]=1 as all these points can be covered by the first tap.

Now we want to create intervals going from the left to the right which will be used to cover the entire garden. The left end of the interval will be the current rightmost point, defined by the variable r, and the length of the interval will be the furthest right endpoint we can get from the current left endpoints, visited by left pointer i. Every time we find a tap covering the right endpoint of this interval i.e. i+r we will update r accordingly and increment our interval count intervals++.

If our starting rightmost end of the interval is still 0, it means we haven’t been able to find a tap covering it, so it’s impossible to cover the intervals, and we return -1.

Code:

The code is written in Python3

def minTaps(n: int, ranges: List[int]) -> int:

coverage = [0] * (n+1) # Set the initial coverage to zero for all the taps
for i in range(n+1):
    left = max(0, i-ranges[i])
    right = i + ranges[i]
    coverage[left:right+1] = [1]*(right-left+1)
    
intervals, r, reachable = 0, 0, 0
while r < n:
    intervals += 1
    max_reach = r
    for i in range(r+1):
        if coverage[i]:
            max_reach = max(max_reach, i+ranges[i]) #update r if the current tap can reach a further point
    if max_reach <= r: # means we can not reach any further right endpoint, so can't cover the entire garden
        return -1
    r= max_reach
return intervals

1