Jump Game (LeetCode #55)

Image by Joseph Frank on Unsplash

This article is part of a series from Nathan Thomas, a full stack software engineer working in San Francisco, CA. Other recent articles from him include Building Your Own Bitcoin Node and Longest Increasing Subsequence.

Introduction

If you’re looking for a quick walkthrough of an optimal solution to the LeetCode Jump Game problem, you’re in the right spot.

This is a question in the Blind 75 LeetCode code challenge list, a group of questions put together by a tech lead at Facebook that’s been touted as a great way to prep for interviews.

Don’t beat yourself up too much if you’re here because it gave you a hard time. Everyone has a hard time with coding challenges sometimes.

Let’s get it started!

Understanding the Problem 🕵🏻‍♂️

The first thing we should always try to do is understand all the rules for our challenge before writing a single line of code (see Polya’s Problem Solving Techniques):

1. We’ll be given a list of nums
2. We’re initially positioned at the first index 0
3. Each value in nums represents the maximum jumps possible from that position
4. We should return True if we reach the end of nums via jumping or else False otherwise
5. nums will have a length of 1 <= len(nums) <= 10^4
6. Values within nums will be 0 <= nums[i] <= 105

I’ll be using Python for the answer for this question since it’s a bit like a universal language — whether you prefer JavaScript, Java, Golang, C, or something else, everyone can “kind of” read Python.

We’ll also be jumping straight into an “optimal” solution. If you’re anything like me, you already attempted this problem before searching for an answer. I’m going to make sure you get a good one.

Okay. I think that’s enough housekeeping items for us to get started!

Initial Problem Setup 🏗

This is yet another dynamic programming problem, but I promise this one is so straightforward that, once we get the solution done, you’re going to remember this one forever.

It turns out that the best way to approach this problem is to use a “greedy” approach for jumping.

Each value in nums represents the maximum amount of jumps from that position. If we keep track of our jumps remaining, subtract 1 each iteration of our loop across nums, and update the jumps we have remaining when the new nums[i] value is larger, we can jump our way across nums while letting this logic handle whether we’ve hit 0 jumps left or not!

If we do hit 0, we can merely return False.

If we make it to the end of the list and exit our loop, we can return True!

Here’s the initial setup for this function:

We’ve set up a variable called jumps_remaining that will be initialized with the first value in our nums list (which is guaranteed to have a length of at least 1). This is because we don’t want to start with 0.

Now, let’s get into setting up our loop! 🔥

Setting Up Our Loop 🔁

The next thing we need to do is use a for loop and iterate over our nums list.

I’m going to use the enumerate function to get access to both the index and the value of each position in nums:

Notice that we immediately update our jumps_remaining with either its current value or the value of the current num, whichever is greater.

The next thing we need to do is to check if our value is 0 even after this update:

We only want to do this if we’re not on the final index of nums. If we have 0 jumps remaining but we’re at the end, that’s a good thing, right?

This is our False case where we return if we can’t keep jumping anymore.

The final thing in our loop we need to do is to subtract 1 from jumps_remaining every iteration. This is us actually performing a jump to the next iteration of the loop!

Finally, we need some code at the end of our function in case we make it to the end of our nums list successfully (e.g. our loop stops running and we never had to return False):

Nice. We can just return True!

This whole thing only iterates through our nums list once, and so it runs in O(n) time complexity. We’re also only using a single variable in memory, so it has a O(1) space complexity.

Conclusion

Nice work. Dynamic programming problems can send you for a bit until they click, but you made it through.

Keep an eye out for the rest of these Blind 75 coding challenges articles. It’s going to be a fun ride.

Feel free to reach out (using the links below) if you want to talk about coding, cool tech, or anything else (I really like book recommendations).

Thanks for reading. 🔥

Nathan

(GitHub, LinkedIn, Twitter, and Personal Site)