The Question

For this article we will be covering Leetcode's '55. Jump Game' question. This question is a classic problem. It's a Greedy Algorithm problem or a Dynamic Programming problem depending on your perspective.

Question:

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.

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.

Explaining The Question

This Question is rated Medium. Which I would say is accurate if you're using the Greedy Algorithm technique. If you're using the Dynamic Programming technique, then this question could be considered a Hard. For this question, we will be using the Greedy Algorithm technique.

What we're being asked to do, is jump from index 0 to the last index of the array. Where each index represents the distance in which it can jump to. So if you're on a index with the value of 2, you can jump 2 indexs forward (Or 1 if you want). This issue at first seems trivial, Brute Force all paths and if we ever reach the last index, we're done. Which mean's this is almost a graph problem. Although, this is not the most efficient way to solve this problem. It's O(n^n) time, it's terribly slow.

Instead, we're going to Greedy and do this O(n) time.

Recommended Knowledge

1. Array
2. Greedy Algorithm
3. Big O Notation

What do we know?

1. We've been given an array of non-negative integers.
2. Each index represents the distance in which we can jump to, we need to jump to the last index.

How we're going to do it:

Initially, you may think, 'Well starting from index 0, keep jumping until we reach the last index and backtrack on a invalid path'. This is a Brute Force solution, a Dynamic Programming solution, that is much alike a Graph Problem with Backtracking.

Instead, we're going to reverse the logic, instead of starting from Index 0, why not start from the last index? We will have a goal post, which is initially the last index, the goal of the goal post is to reach index 0. We will iterate over the array backwards asking, 'Can this element jump to the goal post?' if so, that element becomes the new goal post because it can jump to it. We keep doing this until we've been through the entire array. If we've reached the first index, we can jump to the last index, if the goal post is not, we cannot jump to it.

1. We're going to initialize a goal post, which is initially the last index.
2. We're going to setup a For Loop that iterates over the array backwards.
3. We ask each element 'Can you jump to or over the goal post from here?' if so, we set the goal post to that element.
4. If not, we continue looping.
5. We repeat this logic until we've been through the entire array.
6. Is the goal post now at the first index? If so we can jump to the last index, if not, we cannot jump to it.

Big O Notation:

• Time Complexity: O(n) | Where n is the length of the array.
• Space Complexity: O(1) | As we never allocate any additional memory.

Python Solution

class Solution:
    def canJump(self, nums: List[int]) -> bool:

        goal_post = len(nums) - 1

        for i in range(len(nums) - 2, -1, -1):
            if i + nums[i] >= goal_post:
                goal_post = i

        return (goal_post == 0)

Java Solution

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

        int goal_post = nums.length - 1;

        for (int i = nums.length - 1; i >= 0; i--) {
            int jump_distance = i + nums[i];
            if (jump_distance >= goal_post) {
                goal_post = i;
            }
        }

        return (goal_post == 0) ? true : false;
    }
}

C++ Solution

class Solution {
public:
    bool canJump(vector<int>& nums) {

        int goal_post = nums.size() - 1;

        for (int i = nums.size() - 1; i >= 0; i--) {
            int jump_distance = i + nums[i];
            if (jump_distance >= goal_post){
                goal_post = i;
            }
        }

        return (!goal_post) ? true : false;
    }
};

Javascript Solution

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var canJump = function (nums) {

    let goal_post = nums.length - 1;

    for (let i = nums.length - 1; i >= 0; i--) {
        const jump_distance = i + nums[i];
        if (jump_distance >= goal_post) {
            goal_post = i;
        }
    }

    return !goal_post ? true : false;
};