Minimum Number of Taps to Open to Water a Garden LeetCode Solution

Difficulty Level Hard
Frequently asked in Adobe Amazon Apple Atlassian DE Shaw DocuSign Facebook Flipkart Goldman Sachs Google lyft Mathworks Morgan Stanley Oracle Salesforce Twitter VMware
Razorpay TuSimpleViews 3261

Problem Statement

Minimum Number of Taps to Open to Water a Garden LeetCode Solution – 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 at points [0, 1, ..., n] in the garden.

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.

Example

Test Case 1:

Input:

n = 5

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

Minimum Number of Taps to Open to Water a Garden LeetCode Solution

Explanation

The tap at point 0 can cover the interval [-3,3].

The tap at point 1 can cover the interval [-3,5].

The tap at point 2 can cover the interval [1,3].

The tap at point 3 can cover the interval [2,4].

The tap at point 4 can cover the interval [4,4].

The tap at point 5 can cover the interval [5,5].

Opening Only the second tap will water the whole garden [0,5]

Approach:

First, eliminate all zero since they are useless. Then sort the array base on the first index, then the second index. After that, we get the first tap by using the 1st loop. With the first tap, we try to find the next tap with the farthest endpoint. The next tap should overlap with the pre-tap. After we find the next tap, update the previous tap.

So, the question is basically asking for the minimum taps, that can cover the whole garden.
Algorithm:

  1. dp[i] is the minimum number of taps to water [0, i].
    Initialize dp[i] with max = n + 2
    dp[0] = [0] as we need no tap to water nothing.
  2. Find the leftmost point of the garden to water with a tap i.
  3. Find the rightmost point of the garden to water with a tap i.
  4. We can water [left, right] with one tap,
    and water [0, left - 1] with dp[left - 1] taps.

Code for Minimum Number of Taps to Open to Water a Garden

Java Program

class Solution {
    public int minTaps(int n, int[] A) {
        int[] dp = new int[n + 1];
        Arrays.fill(dp, n + 2);
        dp[0] = 0;
        for (int i = 0; i <= n; ++i)
            for (int j = Math.max(i - A[i] + 1, 0); j <= Math.min(i + A[i], n); ++j)
                dp[j] = Math.min(dp[j], dp[Math.max(0, i - A[i])] + 1);
        return dp[n]  < n + 2 ? dp[n] : -1;
    }
}

C++ Program

class Solution {
public:
    int minTaps(int n, vector<int>& A) {
        vector<int> dp(n + 1, n + 2);
        dp[0] = 0;
        for (int i = 0; i <= n; ++i)
            for (int j = max(i - A[i] + 1, 0); j <= min(i + A[i], n); ++j)
                dp[j] = min(dp[j], dp[max(0, i - A[i])] + 1);
        return dp[n]  < n + 2 ? dp[n] : -1;
    }
};

Complexity Analysis for Minimum Number of Taps to Open to Water a Garden LeetCode Solution

Time Complexity: O(NR), where R = ranges[i] <= 100
Space Complexity: O(N)

Translate »