[Solution]Problem 43: Jump Game (Amazon)
Math, Permutations, Combinatorics, Heaps, Trees
Hey there,
Glad to see you here. You are looking extra finneee today. It must be all the consistent work you’ve been doing. The mental gainzz are showing.
The wedding is finally over. I’m personally not a huge fan of large crowds and lots of noise (esp. over many hours), so I do need to recharge mentally. However, it was nice to see a lot of the family, most of whom have never gotten a chance to interact with me. Now that it is over, I’m going to refocus on the content/traveling/exercising. We have some exciting plans for all the different content streams, so keep your eyes out. You don’t want to miss out.
Getting back to the content for today, we have the solution for the Jump Game problem shared yesterday. As you can see, this does really well. When you see the code and algorithm, you will be blown away.
Problem
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.
Example 1:
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.
Example 2:
Input: nums = [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.
You can test your solution here
[FREE SUBS]To buy the solution for this problem, use any of the following links. The price is 3 USD. Once you send the payment, message me on IG, LinkedIn, Twitter, or by Email:
Venmo: https://account.venmo.com/u/FNU-Devansh
Paypal: paypal.me/ISeeThings
Or you can sign up for a Free Trial Below. If you don’t like it, you can cancel easily, so there’s 0 risk to you -
Step 1: Understanding the Problem
Array questions like this are relatively straightforward to understand. However, it is important to read and understand the problem at a deeper level. This can help us spot possible solutions and optimizations.
I typically like to question the constraints of the problem. This a hangover from my love for philosophy and has helped me a lot with my Machine Learning work.
In our case, a pretty obvious question is to figure out if we can judge if we can reach the end from the current index. Obviously, we can try brute force, testing out every possible configuration from every position. But on average this would lead to a time complexity of O(n^n). If you gave that solution, you would probably be blacklisted from the industry!!
There is one pretty obvious optimization we can make. This won’t cover all the cases but will give us a clear indication of where to go next. Let’s say we were at a particular index. If we know that the value at the index + current location reaches the end, then we know we can reach the end from this index.
if i + nums[i] >= goal: # we can reach the end from this location. This is because we can jump from our current place to the end using just the jumps at our current index.
Let’s say we were at the index 1 for array [1,3,2,0]. Clearly, we can reach the end. This checks out with our rule.
What do we do with this insight? This gives us our next step. If we have an index we can make the jump from then we just need to reach that index. If we can reach that index, we can also reach the end.
Step 2: Reachability
So we now have an easier sub-problem to solve. We need to reach an index that meets our rule above. If we can, reach such an index, we return true. Else we go with false.
Notice this is a recursive structure. We have essentially reduced our solution to a sub-problem with an identical sub-structure (can we reach our target index). The only thing that changes is the target index.
Let’s now conduct further analysis to see if we can tease out the specific details of our algorithm. To do so we will implement one of my favorite problem-solving techniques. It is also through that technique that we will know that our problem is solvable optimally through a Greedy approach. To understand the technique, make sure you review the post How to Spot Greedy Algorithms[Techinque Tuesdays] before continuing.
Done reading? Understand the framework we will be using? Got any doubts about the framework? Resolve them before continuing.
You understand everything? Damn.
For realzies? I see you nodding. I’m going to take you at your word. I’ll be hurt if you lie to me. Let me reveal the super awesome technique now.
Step 3: Function Analysis
OG readers and students from my tutoring know that I love this technique. Analyzing the nature of the problem domain will help you spot optimizations quickly. Practicing your math (esp. analysis of math functions) is a great way to get very good at this skill.
We have already established that this problem has a recursive sub-structure. We also can see that at any index we will have two choices. We can either choose to use the jumps from a previous index. Or start fresh with the jumps from our current index. Solving this correctly involves making the right choice wrt to this decision.
The recursive structure of this problem also gives us an interesting property. The solutions to the subproblem (w/ the earlier magic index) directly lead to the solutions for the main problem. The solution for the subproblem will be identical to the main problem- given this goal index at the end and an array, can we reach this index?
To anyone who practices Greedy Algorithms, you will be licking your lips. This aligns with our framework for spotting Greedy Algo Questions. For this question, the greedy approach can be used optimally. This lets us focus on that approach exclusively and not have to worry about fancier techniques. Peace of mind during your interviews- that you can come up with a simple but efficient solution- is a game-changer, especially when you haven’t come up with your full solution yet.
So let’s come up with the details for the greedy approach.
Step 4: Hashing out the Deets
Let’s look at the rule we can up with earlier again
if i + nums[i] >= goal: # we can reach the end from this location. Obviously, our goal starting off will the last index. Since that is what we want to reach. From there, we want to find those magical indexes, from where we know we can reach the last index. This involves working backward to reach an index that meets the rule above.
Once we reach this magic index, what’s next? Clearly, we need to able to reach that magic index from the locations earlier on in the array. So we will keep searching those earlier places for a magic index to our magic index. Essentially, we have updated our goal to Magic Index #1.
This process will keep going. When should it end? We know that if we our end goal is 0, then we can always reach that index (we start from there). So we will return true. If we do end with a positive goal, that tells us that there is no way we reach that particular goal index from all the earlier values.
Thus we should go backward from the last index, terminating when we reach index 0. Every time an index meets our rule, we have found our magic index. We update the goal to this index. If our goal is also 0 by the end, we return true. Else we return false.
class Solution:
def canJump(self, nums: List[int]) -> bool:
goal = len(nums) -1
for i in range(len(nums) - 2, -1, -1):
if i + nums[i] >= goal:# we can reach the end from this location.
goal = i
return goal == 0Time Complexity- O(N)
Space Complexity- O(1)
Make sure you share your thoughts on this question/solution/any interesting questions/developments in the comments or through my links.
Happy Prep. I’ll see you at your dream job.
Go kill all you Tricky Tactician,
Devansh <3
Reach out to me on:
Instagram: https://www.instagram.com/iseethings404/
Message me on Twitter: https://twitter.com/Machine01776819
My LinkedIn: https://www.linkedin.com/in/devansh-devansh-516004168/
My content:
Read my articles: https://rb.gy/zn1aiu
My YouTube: https://rb.gy/88iwdd
Get a free stock on Robinhood. No risk to you, so not using the link is losing free money: https://join.robinhood.com/fnud75