Pattern 1: Jump Game — Leetcode (Intuition + Mapping + Problems)

Jump Game: (https://leetcode.com/problems/jump-game-ii/description/) You are given a 0-indexed array of integers nums of length n. You are initially positioned at nums[0].

Each element nums[i] represents the maximum length of a forward jump from the index i. In other words, if you are at nums[i], you can jump to any nums[i + j] where:

• 0 <= j <= nums[i] and
• i + j < n

Return the minimum number of jumps to reach nums[n - 1]. The test cases are generated such that you can reach nums[n - 1].

Example 1:

Input: nums = [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2. 
Jump 1 step from index 0 to 1, then 3 steps to the last index.

Intuition:

Think in a way of a ladder, you have given ladders at each index and you have to climb that ladder so that you reach the endpoint.

Why Greedy will work here?

Let's take an example: nums=[2,3,1,1,4]

Here, If we start taking a ladder of 2, the max reach is ( 0 + 2) = 2nd index. This means we can climb to the 2nd index without taking any other ladders.

What will happen when we reach 2nd index? Do we need to keep track of the longest ladder till that? The answer is No, We don't need to take to the longest ladder, we can just keep adjusting one variable which stores the farthest distance we can travel at every index, doesn't matter which ladder we used or go to use. Then we can travel up to the farthest distance from that index and again calculate the farthest distance, we keep doing this unless we reach the end of the array.

while(i<nums.size()&& i <= start){

         max_far=max(max_far,i+nums[i++]);
}

If all the path in between our travel doesn't help much and “we haven’t moved any further then we can say we need to jump”. This jump would be minimum as at any point, we keep maintaining the farthest distance and travel it also. This means we only jump when required.

    int jump(vector<int>& nums) {
        int max_far=0; //farthest distance
        int i=0;
        int start=0; //starting point
        int jump=0;  //jumps
        while(start<nums.size()-1){
            //need to jump
            jump++;

            //checking in the journey what is the farthest point we can go
            while(i<nums.size()&& i <= start){
                max_far=max(max_far,i+nums[i++]);
            }

        // starting point == farthest point, we can say we can't reach to end.
            if(start==max_far)return -1;
            
            start=max_far;

        }
        
        return jump;
        
    }

Similar Problems Mapping:

1. Video Stitching: (https://leetcode.com/problems/video-stitching/)

First, we need to ensure that the array has been sorted by start time. Then say in each step, we have a range [left, right], which means we can only visit the elements within the range in this step. We keep checking the elements until we are at the rightmost position in [left, right] to update “farCanReach”, which means the farthest we can reach in the next step.

int videoStitching(vector<vector<int>>& clips, int time) {
        sort(clips.begin(),clips.end());
      //same logic as Jump game
        int far=0;
        int i=0;
        int start=0;
        int count=0; //jump=count

        while(start<time){
    
            count++;

            while(i<clips.size()&&clips[i][0] <= start){
                far=max(far,clips[i++][1]);
            }
    
            if(start==far)return -1;
            start=far;
        }
        return count;
        
    }

2. Minimum Number of Taps to Open to Water a Garden: (https://leetcode.com/problems/minimum-number-of-taps-to-open-to-water-a-garden/)
For this problem, we just need to construct a new array to move the value into the leftmost point we can water, so the problem becomes Jump Game II. For example, at index I we could water (i — arr[i]) ~ (i + arr[i]). So we store the farthest point we can water at “i — arr[i]”. Then “left” in the range [left, right] is the index, and “right” is the value in arr[index].

int minTaps(int n, vector<int>& ranges) {
        vector<int>v(n+1);

        for(int i=0;i<ranges.size();i++){
             if(ranges[i] == 0) continue;
            int left=max(0,i-ranges[i]);
            v[left]=max(v[left],i+ranges[i]);
        }
        

//same logic as Jump game
        int far=0;
        int i=0;
        int start=0;
        int count=0; //jump=count
        while(start<n){
   
            count++;

            while(i<v.size()&&i<=start){
                far=max(far,v[i++]);
            }

            if(start==far)return -1;
            start=far;
        }
        return count;


 }

“ DP is a technique, Greedy is an art”

Thank you!!