## DEV Community

Samuel Hinchliffe π

Posted on

# 55. Jump Game π

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

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

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;
};

``````