In this article, we’ll be tackling two jump game problems that are available on LeetCode. These are famous coding challenges and can be a little tricky to solve in one try.
We’ll discuss various ways to solve both problems step-by-step with complexity analysis. So, let’s start with the first one.
Jump Game Problem 1
Given an array of non-negative integers, you are initially positioned at the first index of the array. Each element in the array represents your maximum jump length at that position.
Determine if you can reach the last index.
Set Up 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.
Set Up 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.
Constraints
1 <= nums.length <= 3 * 10^40 <= nums[i][j] <= 10^5
How to Solve Jump Game Problem 1
There are many ways to approach this solution. One thing to note here is that we only need to check whether we can reach it or not. We don’t need to care about the number of steps it takes.
We’ll be going with two simple linear solutions. Both of them have similar ideas but differ a little bit in implementation.
Both the solutions would be O(N) time and O(1) space. We won’t need to use dynamic programming (DP) for this solution.
So, let’s start with the first approach, the forward iteration.
We’ll start with the first element of the array and move forward one step each time. We’ll also define a maxReach variable that will keep track of the maximum we can reach from that particular index.
For example, we’re at index 2 and the number at index 2 is four, so the maximum we can reach from here is index 2+4=6.
So, we’ll keep updating maxReach in each iteration. We’ll also keep checking that loop variable I is always less than maxReach, otherwise we’ll be at an index that was not within our reach, i.e., we can’t reach the last element. So, we break out if I exceed maxReach.
To avoid those issues, we’ll check whether i==length of the array which signifies we have reached the end of the array.
bool canJump(vector<int>& nums) {
int i= 0, maxReach=0;
while(i<nums.size() && i<=maxReach){
maxReach = max(i + nums[i], maxReach);
i++;
}
if(i == nums.size())
return true;
return false;
}So, as you can see above, we have our first solution, which isn’t very complicated. We’ll continue updating maxReach and our conditions do the rest of the job. As soon as we reach the end of the array or we surpass maxReach, the loop stops. So, if we have reached the end of the array, we would be at the array’s length that we wanted. Otherwise, we were not able to reach the last element of the array.
So, now let’s move to the second method, backward iteration.
In this approach, we do the same work, but we start from the last element of the array and try to move backwards. If we can successfully reach the first element of the array, it means the result is true, i.e. we can reach the last index of the array.
We’ll define the variable lastreach as the last element of the array. After each iteration, we’ll update the lastreach variable by checking whether the lastreach variable is reachable from that index. If yes, the current index becomes the new lastreach. We keep on doing this until we reach the first element of the array.
Now, we’ll check whether the lastreach variable is equal to zero (index of the first variable), which means we could have reached the last element had we started from the first one.
bool canJump(vector<int>& nums) {
int lastreach = nums.size()-1;
for(int i=nums.size()-2;i>=0;i — )
{
if(i+nums[i]>=lastreach)
lastreach=i;
}
if(lastreach==0)
return true;
return false;
}Both solutions are similar in function. One starts from the beginning of the array and the other from the end of the array. Now, let’s move to Jump Game II, which is a bit more difficult. We’ll be using the same maxReach technique once again with some modifications.
Jump Game Problem 2
Given an array of non-negative integers, you are initially positioned at the first index of the array. Each element in the array represents your maximum jump length at that position. Your goal is to reach the last index in the minimum number of jumps. You can assume that you can always reach the last index.
Set Up 1
Input: nums = [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index.
Set Up 2
Input: nums = [2,3,0,1,4]
Output: 2
Constraints
1 <= nums.length <= 3 * 1040 <= nums[i] <= 105
How to Solve Jump Game Problem 2
There are many ways to solve this problem, but two solutions are the most common. One uses dynamic programming and takes a time of O(N²), while the other solution is a little smarter and operates in O(N) time.
So, let’s review both the approaches and solutions for each one.
The first solution uses dynamic programming and takes a time of O(N²). Be aware that this approach can return a TLE error in LeetCode. Also, this solution uses O(N) space since we need to maintain an extra jumps array, so it’s not optimal.
We’ll first build a new jumps array which will store INT_MAX (maximum value in the respective languages). The purpose of this jumps array is to keep track of the minimum number of jumps needed to reach that particular index.
So, we define jumps[0]=0 since we don’t require any jump to reach the 0th index. Now, we’ll start a loop from the second array element until we reach the last one. For each element, we’ll have an inner loop that runs from the first element until that particular element. For each inner element, we’ll check whether we can reach from that element to the outer element for which the inner loop is running in a single jump. If yes, we’ll update the value of jumps[i] = min(jumsp[i], jumps[j]+1). This allows us to find the minimum number of jumps required to reach that particular index.
This approach relies on previous results and dynamic programming. Since we have one outer loop running through each element of the array, and an inner loop running from 0 to the ith index, it’s O(N²). Also, we have an extra jumps array which consumes O(N) extra space.
int jump(vector<int>& nums) {
vector<int>jumps(nums.size(),INT_MAX);
jumps[0]=0;
for(int i=1;i<nums.size();i++)
{
for(int j=0;j<i;j++)
{
if(nums[j]>=i-j)
jumps[i] = min(jumps[i], jumps[j]+1);
}
}
return jumps[nums.size()-1];
}The second approach is smarter and more optimal because it takes no extra space and uses only O(N) time. In this approach, we define two variables maxReach and steps. Also, we have a jumps variable to count the number of jumps needed.
We define both jumps and steps variable to the value of the first index of the array.
The variable maxReach means the maximum we can reach from that particular index, which is the index plus the value of the index (the jump value.) So, we’ll keep updating it each iteration so that whenever we move forward, the variable stores the maximum we can reach by using maxReach = max(maxReach, nums[i]+i).
Also, at each iteration, we’ll reduce our steps variable by one. As we move forward, we consume one step each time. So, whenever we run out of steps, it means we need to take one jump. So, we increase the jumps variable and also update the steps variable. The steps variable is updated to the value (maxReach — i), which means the difference between a maximum reach possible from that variable, or any variable before it, and the current index. So, we can take those steps and then we’ll need to jump again.
In this solution, we return jumps+1 as our answer since we only jump after we run out of steps, but to perform that, we needed a jump upfront. Also, you need to note that we moved only until the second-to-last element and not the last element, since at the last step, we don’t need to consume one more step. We are already there and don’t need to jump anymore.
We also took care of the edge case when there is only one element in the array. In that case, we don’t need to perform any jumps.
int jump(vector<int>& nums) {
if(nums.size()==1)
return 0;
int maxReach = nums[0];
int steps = nums[0];
int jumps = 0;
for(int i=1;i<nums.size()-1;i++)
{
maxReach = max(maxReach, nums[i]+i);
steps--;
if(steps==0)
{
jumps++;
steps = maxReach - i;
}
}
return jumps+1;
}I hope you learned something out of this post. Go, solve these problems on Leetcode and give jump game III a try.
