Leet Code 55. Tackling Jump I , II , III , IV Game | Cpp ,Java ,Python – Day 3

Leet Code 55.:In this post, we’ll look at two jump game difficulties offered on Leet Code 55. These are well-known coding tasks that might be difficult to complete in a single attempt.We’ll go over numerous approaches to solving both issues step by step using complexity analysis. So, let’s begin with the first.

Day 3 Coding Challenge

Problem 1 of the Jump Game

You are originally positioned at the first index of an array of non-negative numbers. Each array member reflects your maximum jump length at that moment.

Check to see if you can get to the last index.

SET UP 1
Input:nums = [2,3,1,1,4]

Output:true

Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

SET UP 2
Input:nums = [3,2,1,0,4]

Output:false

Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.

How to Solve Problem 1 in Jump Game

Solution – I

There are several approaches to this problem. One thing to keep in mind here is that we simply need to see whether we can get there. We don’t need to worry about how many steps it takes.

We’ll use two straightforward linear solutions. Both have similar ideals but differ somewhat in implementation.Both solutions are O(N) time and O(1) space. This method will not necessitate the usage of dynamic programming (DP).So, let’s begin with the first method, forward iteration.We’ll begin with the first member in the array and work our way forward one step at a time. We’ll also establish a maxReach variable to keep track of how far we can go.

For example, if we are at index 2 and the number at index 2 is four, the most we can get from here is index 2+4=6.

As a result, we’ll keep changing maxReach with each iteration. We’ll also maintain ensuring that loop variable I is always smaller than maxReach, since otherwise we’ll be at an index that wasn’t within our reach, i.e., we won’t be able to reach the last element. So, if I surpass maxReach, we exit.

To prevent these problems, we’ll see if i==length of the array, which indicates that we’ve reached the end of the array.

As you can see above, we have our first answer, which isn’t too difficult. We’ll keep upgrading maxReach, and our conditions will take care of the rest. As soon as   we reach the end of the array or we surpass maxReach, the loop stops. So, if we have reached the end of the array, we would be at the array’s length that we wanted. Otherwise, we were not able to reach the last element of the array.

Code ;

bool canJump(vector<int>& nums) {
    int i= 0, maxReach=0;
    while(i<nums.size() && i<=maxReach){
        maxReach = max(i + nums[i], maxReach);
        i++;
    }
    if(i == nums.size())
        return true;
    return false;
}

Solution – II

Let us now go to the second approach, backward iteration.

We accomplish the same job in this manner, but we start at the end of the array and work our way backwards. If we can successfully reach the initial element of the array, the result is true, i.e. we can reach the array’s final index.

The variable lastreach will be defined as the array’s final element. We’ll update the lastreach variable after each iteration by verifying whether the lastreach variable is reachable from that position. If this is the case, the current index becomes the new lastreach. This is repeated until we reach the first member of the array.

Now we’ll see if the lastreach variable is equal to zero (the index of the first variable), indicating that we could have reached the last element if we had begun from the first.Both options serve the same purpose. One begins at the beginning of the array, whereas the other begins at the end. Let’s now go on to Jump Game II, which is a little more tough. We’ll use the same maxReach approach as before, but with some changes.

Code

bool canJump(vector<int>& nums) {
   int lastreach = nums.size()-1;
   for(int i=nums.size()-2;i>=0;i — )
   {
       if(i+nums[i]>=lastreach)
           lastreach=i;
   }
   if(lastreach==0)
       return true;
   return false;
 }

Java Solution :

class Solution {
    public boolean canJump(int[] nums) {
     int boundary = 0;
     for(int i =0;i<=boundary;i++){
         boundary = Math.max(boundary,i+nums[i]);
         if(boundary >=nums.length-1)
         return true;
     } 
     return false;
    }
}

Python Solution :

class Solution:     
 

    def canJump(self, n: list[int]) -> bool:
        
        if 0 not in n[:-1] or len(n) == 1: return True

        pt = n.index(0)            

        for i in range(len(n)):

            if i <= pt and  i + n[i] > pt: pt = i + n[i]

            if i == pt and not n[i]: return False
            if pt >= len(n)-1      : return True

        return True