Jump Game Problem Statement:

Given a list of maximum jump lengths from different houses, determine if you can reach the last house in one or more jumps starting from the first one.

For example, a maximum jump length of 2 from a house means that you can either jump to the next house or the one after the next.

Example One

{
"maximum_jump_lengths": [2, 3, 1, 0, 4, 7]
}

Output:

1

You can reach the last house in the following way:

Example Two

{
"maximum_jump_lengths": [3, 1, 1, 0, 2, 4]
}

Output:

0

You cannot make it past the house at index 3. A maximum jump length of 0 from that house means that you cannot jump further from it.

Notes

Constraints:

• 0 <= jump length <= 105
• 1 <= number of houses <= 105

‍

We have provided four solutions.

Throughout this editorial, we will refer to the size of the input array as n and to a house as an index. Moreover, let us call an index good if it is possible to reach the last index starting from that index and bad otherwise. Our problem boils down to determining if index 0 is good or bad. We will use the example of [2, 3, 1, 0, 4, 7] and 0-based indexing.

Know how to find the Longest Common Subsequence of Two Strings.

Jump Game Solution 1: Recursive Brute Force

Let us traverse each and every possible path and determine if index 0 is good or bad. For the above example, the recursion tree would be as follows:

Let us do a small optimization here. From a particular index, if any of the reachable indices is good, we do not need to check if any of the other reachable indices are good. In the above example, while checking whether the index 0 is good or not, we do not need to call is_good(2) as is_good(1) is true.

Time Complexity

O(2n)

In the worst case, there will be 2n-2 ways. Apart from the first and last index, there are two choices for every index: either to count it in the solution or not. Here counting an index in the solution means using that index as an intermediary to reach the last index. In other words, to reach the last index, either we use a certain index as an intermediary or we don't. Hence each index, apart from the first and last index, has two choices.

Auxiliary Space Used

O(n): In the worst case, the maximum recursive stack size would be n.

Space Complexity

O(n)

Input takes O(n)

Auxiliary space used: O(n)

Output takes O(1)

Total space complexity: O(n) + O(n) + O(1) = O(n).

Code for Jump Game Solution 1: Recursive Brute Force

/*
Asymptotic complexity in terms of size of `maximum_jump_lengths` `n`:
* Time: O(2^n).
* Auxiliary space: O(n).
* Total space: O(n).
*/
// The function returns true if we can reach the last index starting from the current index.
// Otherwise, it returns false.
bool is_good(int index, vector &maximum_jump_lengths) {
   if (index == maximum_jump_lengths.size() - 1) {
       return true;
   }
   for (int i = 1; i <= maximum_jump_lengths[index] && index + i < maximum_jump_lengths.size(); i++){
       if (is_good(index + i, maximum_jump_lengths)) {
           return true;
       }
   }
   return false;
}
bool can_reach_last_house(vector &maximum_jump_lengths) {
   return is_good(0, maximum_jump_lengths);
}

Jump Game Solution 2: Recursive Memoization

We can notice that we have a lot of redundant function calls in the previous solution. Once we determine that an index is good or bad, it is going to remain either good or bad. So we can store that result and use it whenever needed. This technique is called memoization. Let us store the result of is_good(i) at position i in a new auxiliary array of size n.

Time Complexity

O(n2): In the worst case, for each index, we iterate all its succeeding indices to find if at least one is good.

Auxiliary Space Used

O(n): We use an additional array of size n to store the results.

Space Complexity

O(n)

Input takes O(n)

Auxiliary space used: O(n)

Output takes O(1)

Total space complexity: O(n) + O(n) + O(1) = O(n).

Code for Jump Game Solution 2: Recursive Memoization:

/*
Asymptotic complexity in terms of size of `maximum_jump_lengths` `n`:
* Time: O(n^2).
* Auxiliary space: O(n).
* Total space: O(n).
*/
// The function returns true if we can reach the last index starting from the current index.
// Otherwise, it returns false.
bool is_good(int index, vector &maximum_jump_lengths, vector &is_good_cached) {
   if (index == maximum_jump_lengths.size() - 1) {
       return true;
   }
   for (int i = 1; i <= maximum_jump_lengths[index] && index + i < maximum_jump_lengths.size(); i++) {
       if (is_good_cached[index + i] == -1) {
           is_good_cached[index + i] = is_good(index + i, maximum_jump_lengths, is_good_cached);
       }
       if (is_good_cached[index + i])
           return true;
   }
   return false;
}
bool can_reach_last_house(vector &maximum_jump_lengths) {
   // Initialize by -1. -1 denotes unknown, 0 denotes bad, 1 denotes good.
   vector is_good_cached(maximum_jump_lengths.size(), -1);
   return is_good(0, maximum_jump_lengths, is_good_cached);
}

Jump Game Solution 3: Iterative Dynamic Programming

Observe that the result (good or bad) of any index is dependent only on the results of greater indices. This implies that we can calculate the result for a certain index if we have the results of indices greater than it. This idea suggests we traverse the indices in reverse order, starting from the last one. This approach eliminates the need for recursion.

Let’s look at this approach for the above example:

We will represent a good index by “G,” a bad index by “B,” and an unvisited index by “-.” These characters we only use to explain the solution here.

Step 1

Index

0

1

2

3

4

5

Result

-

-

-

-

-

G

The last index will always be good.

Step 2

Index

0

1

2

3

4

5

Result

-

-

-

-

G

G

The maximum jump length at the 4th index is 4. The 5th index is a good index that can be reached from the 4th index. Hence, the 4th index is also a good index.

Step 3

Index

0

1

2

3

4

5

Result

-

-

-

B

G

G

The maximum jump length from the 3rd index is 0. No good index can be reached from the 3rd index. Hence, the 3rd index is a bad index.

Step 4

Index

0

1

2

3

4

5

Result

-

-

B

B

G

G

The maximum jump length from the 2nd index is 1. Only the 3rd index (bad) can be reached from the 2nd index. As no good index can be reached from the 2nd index, it is a bad index.

Step 5

Index

0

1

2

3

4

5

Result

-

G

B

B

G

G

The maximum jump length from the 1st index is 3. Indices 2, 3, and 4 can be reached from the 1st index. Among these indices, at least one index (4th) is a good index, and therefore, the 1st index is good.

Step 6

Index

0

1

2

3

4

5

Result

1

1

0

0

1

1

The maximum jump length from the index 0 is 2. Indices 1 and 2 can be reached from index 0. Among these indices, at least one index (1st) is a good index, and therefore, the 1st index is good.

Index 0 is good, which means the last index can be reached from it.

Time Complexity

O(n2): In the worst case, for each index, we iterate all its succeeding indices to find if at least one is good.

Auxiliary Space Used

O(n): We use an additional array of size n to store the results.

Space Complexity

O(n)

Input takes O(n)

Auxiliary space used: O(n)

Output takes O(1)

Total space complexity: O(n) + O(n) + O(1) = O(n).

Code for Jump Game Solution 3: Iterative Dynamic Programming:

/*
Asymptotic complexity in terms of size of `maximum_jump_lengths` `n`:
* Time: O(n^2).
* Auxiliary space: O(n).
* Total space: O(n).
*/
bool can_reach_last_house(vector &maximum_jump_lengths) {
   // Initialize with zeros (bad index)
   vector is_good_cached(maximum_jump_lengths.size(), 0);
   is_good_cached.back() = 1;
   for (int i = maximum_jump_lengths.size() - 2; i >= 0; i--) {
       for (int j = i + 1; j <= i + maximum_jump_lengths[i]; j++) {
           if (is_good_cached[j]) {
               is_good_cached[i] = 1;
               break;
           }
       }
   }
   return is_good_cached[0];
}

‍Check If the Number is a Palindrome.

Jump Game Solution 4: Iterative Greedy

Let us define the approach of the previous solution in a slightly different way. For each index X, we look for the first succeeding good index that is inside the farthest possible jump. If there is no good index in the reachable range, we mark index X bad.

The intuition behind this solution is to only store the leftmost good index we have found so far instead of the whole array of values used in the previous solution. Initially, leftmost_good_index = n - 1 as the last index is always good. For any index X, if the leftmost_good_index is within (inclusive) the farthest reachable index from X, then it is a good index. As we check indices one by one, the leftmost_good_index remains unchanged if the current index is bad. Otherwise, it is updated to the current index. After checking all indices starting from the last, if leftmost_good_index = 0, it means that the last index can be reached from index 0.

Let us walk through this algorithm for the same example of [2, 3, 1, 0, 4, 7]:

Step 1

current_index = 5

leftmost_good_index = 5

Step 2

current_index = 4

The farthest reachable index from the current index is 5. The leftmost_good_index is inside this range, therefore we update our leftmost_good_index to 4.

leftmost_good_index = 4

Step 3

current_index = 3

The farthest reachable index from the current index is 3. The leftmost_good_index is outside this range.

leftmost_good_index = 4

Step 4

current_index = 2

The farthest reachable index from the current index is 3. The leftmost_good_index is outside this range.

leftmost_good_index = 4

Step 5

current_index = 1

The farthest reachable index from the current index is 4. The leftmost_good_index is inside this range, therefore we update our leftmost_good_index to 1.

leftmost_good_index = 1

Step 6

current_index = 0

The farthest reachable index from the current index is 2. The leftmost_good_index is inside this range, therefore we update our leftmost_good_index to 0.

leftmost_good_index = 0

leftmost_good_index = 0 which means the last index can be reached from index 0.

Time Complexity

O(n): We do a constant amount of work per index.

Auxiliary Space Used

O(1)

Space Complexity

O(n)

Input takes O(n)

Auxiliary space used: O(1)

Output takes O(1)

Total space complexity: O(n) + O(1) + O(1) = O(n).

Code for Jump Game Solution 4: Iterative Greedy:

/*
Asymptotic complexity in terms of size of `maximum_jump_lengths` `n`:
* Time: O(n).
* Auxiliary space: O(1).
* Total space: O(n).
*/
bool can_reach_last_house(vector &maximum_jump_lengths) {
   int leftmost_good_index = maximum_jump_lengths.size() - 1;
   for (int i = maximum_jump_lengths.size() - 2; i >= 0; i--) {
       if (maximum_jump_lengths[i] + i >= leftmost_good_index) {
           leftmost_good_index = i;
       }
   }
   if (leftmost_good_index == 0) {
       return true;
   }
   return false;
}

We hope that these solutions to the Jump Game problem will help you level up your Dynamic Programming skills. Companies such as Facebook, Amazon, Microsoft, Google, eBay, etc., include Jump Game interview questions in their tech interviews. 

If you are preparing for a tech interview at FAANG or any other Tier-1 tech company, register for Interview Kickstart’s FREE Webinar to understand the best way to prepare. 

Interview Kickstart offers interview preparation courses taught by FAANG+ tech leads and seasoned hiring managers. Our programs include a comprehensive curriculum, unmatched teaching methods, FAANG+ instructors, and career coaching to help you nail your next tech interview. 

We offer 17 interview preparation courses, each tailored to a specific engineering domain or role, including the most in-demand and highest-paying domains and roles, such as:

• Back-end Engineering Interview Course
• Front-end Engineering Interview Course
• Full Stack Developer Interview Course

To learn more, register for the FREE Webinar.