< Back





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

Similar to ~ 1024. Video Stitching, we have a garden and we want to cover the
entire garden in water. At each location in the garden is a water tap that covers
(i - ranges[i], i + ranges[i]) space. We want to find the minimum number of taps we need to open to
cover the entire garden.

I originally solved this question like Video Stitching by sorting the taps by their start and
end points - descending. Instead of using the original ranges, I only care about covering 0-n space,
therefore the (start, end) of the taps are (max(0, i - ranges[i]), min(n, i + ranges[i])).

I then looped through the sorted array of taps, keeping track of the maximum end point of the taps
seen so far, and only adding a tap if the current tap's start point is less than the maximum end
point seen so far. If the maximum end point ever surpasses n, we can return the number of taps
opened.

We can solve this faster by using the same greedy approach, but instead of sorting the taps, we use
counting sort in O(n) time. We maintain an array of size n + 1, where each index represents the start
point of the garden, and the value at that index represents the maximum endpoint of coverage for that
section of the garden. We maintain the number of taps we've chosen so far, as well as the current
endpoint and the next endpoint we can reach.

We loop through the array of tap locations from 0 to n. If the tap location is ever greater than the
next endpoint we can reach, we know that we can't get full coverage, and we return -1. If the tap
is greater than the current endpoint, we update the current endpoint to the next endpoint we can
reach and select this tap. We then update the next endpoint, maximizing for the reach of the current
tap.

The solution is as follows:


  class Solution:
      def minTaps(self, n: int, ranges: List[int]) -> int:
          max_reach = [0] * (n + 1)

          for i in range(len(ranges)):
              start, end = max(0, i - ranges[i]), min(n, i + ranges[i])
              max_reach[start] = max(max_reach[start], end)

          ans = curr_end = next_end = 0

          for i in range(n + 1):
              if i > next_end:
                  return -1

              if i > curr_end:
                  ans += 1
                  curr_end = next_end

              next_end = max(next_end, max_reach[i])

          return ans


_ Time Complexity:

  O(n) - We have to iterate through the input.

_ Space Complexity:

  O(n) - We store the max reach of each tap.