Table of Contents
Problem Statement
Jump Game Leetcode Solution – 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:
Input 1:
nums = [2, 3, 1, 1, 4]
Output 1:
true
Input 2:
nums = [3, 2, 1, 0, 4]
Output 2:
false
Explanation for Jump Game Leetcode Solution:
i) For Input 1, we can jump 1 step from index 0 to 1, then 3 steps to the last index.
ii) For Input 2, we can try different ways but every time we will arrive at index 3. Its maximum jump length is 0. So we can’t go further from that index. So it is impossible to reach the last index.
Approach
Idea
- At every step, we can check what is the maximum index we can reach from that index.
- It’s like a greedy approach.
- In the end, we can check if the maximum index reached is the last index of the array.
- If both are the same, we can return true otherwise we can return false.
Code for Jump Game Leetcode Solution
Java Program
class Solution {
public boolean canJump(int[] nums) {
int i = 0;
for (int reach = 0; i < nums.length && i <= reach; ++i)
reach = Math.max(i + nums[i], reach);
return i == nums.length;
}
}C++ Program
class Solution {
public:
bool canJump(vector<int>& nums) {
int n = nums.size();
int i = 0;
for (int reach = 0; i < n && i <= reach; ++i)
reach = max(i + nums[i], reach);
return i == n;
}
};Complexity Analysis for Jump Game Leetcode Solution
Let N be the length of the input array.
Time complexity: O(N)
We are only iterating over the input array. So it will take O(N) time.
Space complexity: O(N)
We are using only constant space. So the space complexity is O(1).