The ‘Jump Game’ Software Engineering Problem

A simple, optimized solution for a popular algorithms question.

Photo by Walker Fenton on Unsplash

The Problem

Jump game can be found on leetcode here.

You are given an array of integers. You start at the first element in the array, and each element in the array represents the maximum number of indexes you can “jump.” You need to determine if it is possible to jump to the end of the array. Here are some examples.

In my snippet here, I’ve got the indexes on the first line and the actual array of integers on the second line. Having the indexes handy and visible like this helps me a lot when I’m trying to get a deep understanding of an algorithms problem that involves an array. I’ll be formatting my examples like this from here on.

 0  1  2  3  4
[2, 3, 1, 1, 4]

For this example, the result would be true. You can jump like this:

 0  1  2  3  4
[2, 3, 1, 1, 4]
 ^
 0  1  2  3  4
[2, 3, 1, 1, 4]
       ^
 0  1  2  3  4
[2, 3, 1, 1, 4]
          ^
 0  1  2  3  4
[2, 3, 1, 1, 4]
             ^

Or like this:

 0  1  2  3  4
[2, 3, 1, 1, 4]
 ^
 0  1  2  3  4
[2, 3, 1, 1, 4]
    ^
 0  1  2  3  4
[2, 3, 1, 1, 4]
             ^

Here is another example:

 0  1  2  3  4
[3, 2, 1, 0, 4]

For this example, the result would be false. You will always end at index 3. The value there is 0 so you’re stuck, and no index before that index has a high enough value to jump past it.

The Solution

It is possible to solve this with O(n) time and O(1) memory. We’re going to use a Greedy Algorithm and start at the end of the array. You could start at the beginning of the array and use recursion to test every possible jump path. That’s not going to be as good from a time complexity stand point though.

The consequence of using a greedy algorithm here is that we may not find the most optimal jump path — but that doesn’t matter. We just need to determine if a jump path exists. If tasked with finding the most optimal jump path, I would consider using recursion, but I haven’t spent too much time thinking about that.

Let’s start by creating a variable that holds the last index of the array. Then, we’re going to loop through the array backwards starting from the second to last element and ending with the first element. My solution here is in TypeScript.

function canJump(nums: number[]): boolean {
    let jump = nums.length - 1;
    for (let i = nums.length - 2; i >= 0; i--) {
    }
}

Each time we iterate in our for loop, we’re going to see if we can reach the last index we stored as jump from the current index i. If so, we’ll store it as jump.

 0  1  2  3  4
[2, 3, 1, 1, 4]
// i = 3
// jump = 4
// can you reach index 4 from index 3 if its value is 1?
// yes, so jump becomes 3
// next in loop
// i = 2
// jump = 3
// can you reach index 3 from index 2 if its value is 1?
// yes, so jump becomes 2
// next in loop
// i = 1
// jump = 2
// can you reach index 2 from index 1 if its value is 3?
// yes, so jump becomes 1
// next in loop
// i = 1
// jump = 2
// can you reach index 2 from index 1 if its value is 3?
// yes, so jump becomes 1
// next in loop
// i = 0
// jump = 1
// can you reach index 1 from index 0 if its value is 2?
// yes, so jump becomes 0
// jump = 0

Here’s what that looks like in our TypeScript solution:

function canJump(nums: number[]): boolean {
    let jump = nums.length - 1;
    for (let i = nums.length - 2; i >= 0; i--) {
        if (i + nums[i] >= jump) {
            jump = i;
        }
    }
}

So how do we know if we’ve jumped across the entire array successfully, and not just part of the array? Let’s consider an example where the result is false.

 0  1  2  3  4
[3, 2, 1, 0, 4]
// i = 3
// jump = 4
// can you reach index 4 from index 3 if its value is 0?
// no, so jump remains 4
// next in loop
// i = 2
// jump = 4
// can you reach index 4 from index 2 if its value is 1?
// no, so jump remains 4
// next in loop
// i = 1
// jump = 4
// can you reach index 4 from index 1 if its value is 2?
// no, so jump remains 4
// next in loop
// i = 1
// jump = 4
// can you reach index 4 from index 1 if its value is 2?
// no, so jump remains 4
// next in loop
// i = 0
// jump = 4
// can you reach index 4 from index 0 if its value is 3?
// no, so jump remains 4
// jump = 4

We know we’ve jumped across the entire array when jump is 0 after the for loop. So let’s add that to the code for our final solution:

function canJump(nums: number[]): boolean {
    let jump = nums.length - 1;
    for (let i = nums.length - 2; i >= 0; i--) {
        if (i + nums[i] >= jump) {
            jump = i;
        }
    }
    return jump === 0;
}

I wrote this article because I wanted to improve my own understanding of this problem. I hope I helped improve your understanding of it as well.

Thank you for reading!