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

Option 0: O(n) greedy

template

class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        taps = []
        for i, r in enumerate(ranges):
            left, right = max(0, i-r), min(n, i+r)
            taps.append([left, right])
        taps.sort()
        
        curEnd, nextEnd = 0, 0
        cnt = 0
        for left, right in taps:
            if nextEnd < left:
                return -1
            
            if curEnd < left:
                cnt += 1
                curEnd = nextEnd
                if curEnd >= n:
                    return cnt
            
            nextEnd = max(nextEnd, right)
        
        if nextEnd < left:
            return -1
        
        if curEnd >= n:
            return cnt
        return cnt + 1

pretty much 45. Jump Game II

Option 1: greedy

why for i in range(n): instead of for i in range(n+1): at the point i == n-1, there are 3 cases:

curMaxPos < n-1: return -1
curMaxPos == n-1: return count+1
curMaxPos > n-1: return count

class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        nextIdx = [-1] * (n+1)
        for i, r in enumerate(ranges):
            left = max(i-r, 0)
            nextIdx[left] = max(nextIdx[left], i+r)
        
        count = 0
        curMaxPos = nextMaxPos = 0
        for i in range(n):
            nextMaxPos = max(nextMaxPos, nextIdx[i])
            if curMaxPos < i:
                return -1
            elif curMaxPos == i:
                count += 1
                curMaxPos = nextMaxPos
        return count

Option 2: DP

initialize dp to n+2 as the max number we need is n+1 so n+2 means unreachable

dp[i] : min number of taps required to water range [0: i+1]

dp[j] = min(dp[j], dp[left] + 1) => there might be position x between left and j where we can add this tap to water j. However, dp[x] >= dp[left]

class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        dp = [0] + [n+2] * n
        for i, r in enumerate(ranges):
            left, right = max(i-r, 0), min(i+r, n)
            for j in range(left+1, right+1):
                dp[j] = min(dp[j], dp[left] + 1)
        return dp[-1] if (dp[-1] < n+2) else -1

1326. Minimum Number of Taps to Open to Water a Garden - cocoder39/coco39_LC GitHub Wiki