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.
Keep reading with a 7-day free trial
Subscribe to Technology Made Simple to keep reading this post and get 7 days of free access to the full post archives.