https://leetcode.com/problems/jump-game/
Problem Statement:
Given an array of non-negative integers nums, 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 are able to reach the last index.
Examples
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.Idea:
Here we can keep track of the left most index. If the current element can get at least to the left most index, it becomes the left most index. Therefore if we go right to left, if at the end the left most index is 0, we know we can jump to the end.
Greedily update the left most index.
Solution:
class Solution {
public:
bool canJump(vector<int>& nums) {
int leftMostIndex = nums.size() - 1;
for(int i = nums.size() - 1; i >= 0; --i) {
// if we can at least reach the left most index, make i the left most index.
if(i + nums[i] >= leftMostIndex) {
leftMostIndex = i;
}
}
// if left most index ends at zero, we can jump to the end.
return leftMostIndex == 0;
}
};
Complexity Analysis:
Time
O(N) time. It is a one time linear pass over the input array.
Memory
O(1) memory.
Side Note: Original DP Implementation I went with
class Solution {
public:
bool canJump(vector<int>& nums) {
if(nums.empty()) {
return false;
}
vector<int> dp;
dp.resize(nums.size(), 0);
dp[nums.size() - 1] = 1;
// start at the second to last, we can always reach the last element
for(int i = nums.size() - 2; i >= 0; --i) {
int num_to_check = nums[i];
int cur_offset = 1;
while( ((cur_offset + i) < nums.size()) && (num_to_check > 0) ) {
if(dp[i + cur_offset] == 1) {
dp[i] = 1;
break;
}
cur_offset += 1;
num_to_check -= 1;
}
}
return dp[0];
}
};
Time
O(N^2) time.
Memory
O(N) memory.
Comments
Nothing yet.