DEV Community 👩‍💻👨‍💻

Prashant Mishra
Prashant Mishra

Posted on • Originally published at leetcode.com

Jump game leetcode problem

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.

Solution: Dp memoization (top down approach)

class Solution {
    public boolean canJump(int[] nums) {

       // we will solve it using dp
        boolean[] dp = new boolean[nums.length];
        /*
        Fill the dp indices with true , as true will tell us that this
        index has not been explored. And if after the exploration this index is still true it will mean that we can reach the last index from current index*/
        Arrays.fill(dp,true); 
        return solve(nums,0,dp);
    }
    public boolean solve(int[] nums,int index, boolean[] dp){
        // base cases
        if(index == nums.length-1) return true;
        if(index>=nums.length) return false;
        if(dp[index]==false) return false; // this means that this index has been explored and it does not lead to the last index

        // at given index i we jump to i+1 or i+2 .... till i+k <=i+nums[i];
        /*
        Example :[2,3,1,1,4] 
        if i =0, nums[i] = 2
        we can jump to i+1 i.e. 0+1 (less than i+nums[i] which is 2) or 0+2 (which is equals to 2) */
        for(int i = index+1;i<=index+nums[index];i++){
            if(dp[i]){ // traverse only if its true, means its has not been traversed 
                dp[i] = solve(nums,i,dp);
                // even after traversal if it comes as true , it will mean that last index is reachable from this index.
                if(dp[i]) return true;
            }


        }
        return false; // return false if the last index is not reachable.
    }
}
Enter fullscreen mode Exit fullscreen mode

Top comments (0)

🌚 Life is too short to browse without dark mode