hi, let Avik connect you.
** You can give your thought about this content and request modifications if needed from Ask For Modifications page. Thank You.
** You can check all the posts on the Posts page.
** More about me in the About Me section.
Jump Game
Problem: 55. Jump Game
Problem Link: leetcode.com/problems/jump-game/
Approach:
Solved this problem in both DP and Greedy approaches.
DP Approach:
I have started traversing from the (n-1)'th position of the array.
While moving backward, I make them marked as true as I am able to visit those indexes from the current position.
In the end, I just iterate over the marked array to check if the is any unmarked cell.
If there is then returned False.
Or returned True at the end.
Greddy Approach:
Started moving from the 0th position.
Checked the maximum between current_max and (i+nums[i]).
If current_max becomes less than or equal to i, then returned False.
Why? Because whatever the situation, from any previous index it is not possible to jump beyond i.
Otherwise returned True at the end.
Time and Space Complexity:
Time Complexity: O(N)
Space Complexity: O(1)
Code [C++] [DP | O(N²)]
class Solution {
public:
bool canJump(vector<int>& nums) {
int n = nums.size();
bool possible[n+1];
memset(possible, false, sizeof(possible));
for(int i=n-1; i>=0; i--){
if(!possible[i]){
int next = i + nums[i];
// if(next >= n-1 || possible[next]) possible[i] = true;
if(next >= n-1){
for(int j=i; j<=n-1; j++){
// if(possible[j]) break;
possible[j] = true;
}
}
else{
for(int j=i; j<next; j++){
// if(possible[j]) break;
possible[j] = true;
}
}
}
}
for(int i=0; i<n; i++){
if(!possible[i]) return false;
}
return true;
}
};
Code [C++] [Greedy | O(N)]
class Solution {
public:
bool canJump(vector<int>& nums) {
int maxVal = 0;
for(int i=0; i<nums.size()-1; i++){
maxVal = max(maxVal, nums[i] + i);
if(maxVal <= i) return false;
}
return true;
}
};