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

Sarthak Sehgal · April 29, 2020

hard   greedy   dynamic programming

I highly recommend solving LC 1024. Video Stitching (solution) and LC 45. Jump Game II (solution) before trying this problem as it can be reduced to either of the two problems.

Approach 1: Jump Game II

The question can be converted into the form of Jump Game II.

  1. The range each tap covers is: max(0, i-ranges[i]) (say l) to min(n, i+ranges[i]) (say r). Think of this range as a jump starting from the index max(0,i-ranges[i]) with maximum reach till min(n, i+ranges[i]) - min(0, i-ranges[i]).
  2. To do this, we define a new array jumps where jumps[l] = max(jumps[l], r-l). Now our problem boils down to calculating the minimum number of jumps required to reach the end of array.
  3. The main idea is based on greedy. Let’s say the range of the current jump is [curBegin, curEnd], curFarthest is the farthest point that all points in [curBegin, curEnd] can reach. Once the current point reaches curEnd, then trigger another jump, and set the new curEnd with curFarthest, then keep the above steps.
int minTaps(int n, vector<int>& ranges) {
    vector<int> jumps(n+1, 0);

    for (int i=0; i<ranges.size(); i++) {
        int l = max(0, i-ranges[i]);
        int r = min(n, i+ranges[i]);
        jumps[l] = max(jumps[l], r-l);
    }

    for (auto i : jumps)
        cout<<i<<" ";
    cout<<endl;

    // See Jump Game II
    int count = 0, curEnd = 0, curFarthest = 0;
    for (int i = 0; i<jumps.size()-1; i++) {
        if (i>curFarthest)
            return -1;

        curFarthest = max(curFarthest, i + jumps[i]);

        if (i == curEnd) {
            count++;
            curEnd = curFarthest;
        }
    }

    return curFarthest >= n ? count : -1;
}

Approach 2: Video Stitching

This problem can also be reduced into video stitching. Instead of jumps, just take them to be intervals. The range each tap covers is: max(0, i-ranges[i]) (say l) to min(n, i+ranges[i]) (say r). Think of this range as a clip segment [l, r] and apply the same logic as in Video Stitching.

Recommended: See solution of LC 1024. Video Stitching.

Twitter, Facebook