55. Jump Game

Jump Game

Problem Description

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 <= 104
• 0 <= nums[i] <= 105

Approach) Greedy

var canJump = function(nums) {
    let goal = nums.length - 1
    
    for(let i = nums.length - 1; i >= 0; i--){
        // once you reached to the last index, you update that the goal to current index
        // because current index proved that can reached to the last index ( so now we treat current index as last index)
        
        if(i + nums[i] >= goal) goal = i // if you can't understand this part, simply just draw yourself (worth than speaking of mouth)
    }
	
	// goal == 0 means starting index of 0 can reach to the last index
    return goal == 0
};

Approach) Recursion

var canJump = function(nums) {
    const memo = new Map()
    return backtrack(0)
    
    function backtrack(i){
		if(memo.has(i)) return memo.get(i)
		
		// return false if you jump over the last index
		if(i >= nums.length) return false

		// return true if you jump into the last index
		if(i == nums.length - 1) return true

		// you want to give it a try to jump one or two or three ...etc, in every possible steps at max of nums[ i ]
		for(let s = 1; s <= nums[i]; s++){
			if(i + s < nums.length && backtrack(i + s)) return true
		}
        
		// if current index cannot reach to last index, then we set that current index to false
        memo.set(i, false)
		
		// return false since we cannot reach to last index
        return false
    }
};

Approach) Two Line Javascript 

The core problem is to check whether we can jump all the way to the end or more, and is easily accomplished by updating a "furthest index we have reached so far" variable. But there is one important gotcha.

The problematic situation is if we have e.g. [3,0,0,0,2], in which case the first 3 never allows us to jump to the last 2.

Thus we check for acc >= i, so in the above case, the 2 is at index = 4, while acc = 3... which is short. So we shouldn't update the acc with index=4 + num=2 = 6.

• acc just means the furthest index we have reached so far, common parlance for the "accumulator" in a reduced call
  
  

function canJump(nums) {
    if(!nums || !nums.length) return false;
    return nums.reduce((acc, num, i)=>acc >= i ? Math.max(acc, i+num) : acc, 0) >= nums.length - 1;
}

Approach) BFS (breadth-first search)

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var canJump = function(nums) {
    /*
    Approach: Use BFS
    If we are at index 'i' and it has value 'n' then we can assume there is  an edge from index 'i' to every node till index 'i'+n
    */
    let queue=[],node,visited={},length,nextIndex;
    length = nums.length;
    visited[0]=true;
    queue.push(0);
    while(queue[0]!==undefined){
        node = queue.shift();
        if(node === length-1){
            return true;
        }
        for(let i=1;i<=nums[node] && i<length;i++){
            nextIndex = node+i;
            if(nextIndex===length-1){
                return true;
            }
            if(visited[nextIndex]===undefined){
                visited[nextIndex]=true;
                queue.push(nextIndex);
            }
        }
    }
    return false;
};

Approach) Dynamic Programming (DP)

var canJump = function(nums) {
    const dp = new Array(nums.length).fill();
    dp[0] = true;
    
    for(let j = 1; j < nums.length; ++j) {
        dp[j] = false;
        for(let i = 0; i < j; ++i) {
            if(dp[i] && i + nums[i] >= j) {
                dp[j] = true;
                break;
            }
            
        }
    }
    return dp[nums.length -1];
};

Conclusion

That’s all folks! In this post, we solved LeetCode problem 55. Jump Game

I hope you have enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.

In this blog, I have tried to collect & present the most important points to consider when improving Data structure and logic, feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!