Tuesday, July 26, 2022

JUMP GAME (LEETCODE)

July 26, 2022 1 Comment

JUMP GAME (LEETCODE)

You are given an integer array nums. You are initially positioned at the array's first index, and each element in the array represents your maximum jump length at that position.

Return true if you can reach the last index, or false otherwise.

Example 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.

Example 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.

Constraints:

1 <= nums.length <= 10⁴
0 <= nums[i] <= 10⁵

The above problem ask to write a program to validate then can we reach to the last index of the array with the maximum number of jumps equals to the value at current index starting from the beginning.

What we can do to solve this is to take a variable named max_reachable and store the maximum index that can be reached from start till the end and calculating the maximum index storing it in the variable (max_reachable).

If the max_reachable variable is less than the current index while traversing the array then it will return false as it would not be possible to reach the last index in that case.

(max_reachable variable stores the ,maximum index reached while traversing the array and it replaces with the new maximum value while traversing.)

Code (Java):

   public static Boolean canJump2(int[] nums){

        int reachable = 0;

        for(int i = 0; i < nums.length; i++){
            if(reachable < i)
                return false;
            

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

        return true;

    }


    public static int max(int i, int j){
        if(i > j)
            { 
                return i;
            }
        return j;
        
    }