PROBLEM DESCRIPTION You are given an integer array. 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: array = [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: array = [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.
PROBLEM (link: https://leetcode.com/problems/jump-game/) I have used recursion to solve this problem which results in taking more time. So, is there any way I could do this problem effectively in C programming with any other logic. My program
bool isValid(int i,int* arr, int n, int* dp){
if(i==n-1)return true;
else if(i>=n)return false;
else if(dp[i]!=-1)return dp[i]==1?true:false;
for(int jump=1;jump<=arr[i];jump++){
if(isValid(i+jump, arr, n,dp)){
dp[i]=1;
return true;
}
}
return dp[i]=0;
}
bool canJump(int* nums, int numsSize) {
int* dp = (int*)malloc(sizeof(int)*numsSize);
for(int i=0;i<numsSize;i++)dp[i]=-1;
return isValid(0, nums, numsSize, dp);
}
This can be done very efficiently with a single iteration over the array.
|---------->|
|------>|
|-->| |--->
+---+---+---+---+---+
| 3 | 2 | 1 | 0 | 4 |
+---+---+---+---+---+
The reason [3,2,1,0,4] fails the test is that nothing crosses the boundary between the 4th and 5th element.
[Try to solve yourself before reading on.]
The key is calculating the maximum reachable index as you iterate through the array.
[Try to solve yourself before reading on.]
Iterate through the array once. If the current index is larger than the current maximum reachable index, return false. If you reach the end of the array, return true.
The current maximum reachable index is the maximum of the reachable indexes of the elements you have encountered. The reachable index of an element is its index plus its value.
| index | 0 | 1 | 2 | 3 | 4 |
| value | 2 | 3 | 1 | 1 | 4 |
| ok? (i≤mri?) | yes (0≤0) | yes (1≤2) | yes (2≤4) | yes (3≤4) | yes (4≤4) |
| reachable index | 2 | 4 | 3 | 4 | 8 |
| max reachable index | 2 | 4 | 4 | 4 | 8 |
| index | 0 | 1 | 2 | 3 | 4 |
| value | 3 | 2 | 1 | 0 | 4 |
| ok? (i≤mri?) | yes (0≤0) | yes (1≤3) | yes (2≤3) | yes (3≤3) | no (4>3) |
| reachable index | 3 | 3 | 3 | 3 | |
| max reachable index | 3 | 3 | 3 | 3 |
[Try to solve yourself before reading on.]
size_t max_reachable = 0;
for ( size_t i = 0; i < n; ++i ) {
if ( i > max_reachable )
return false;
size_t reachable = i + nums[ i ];
if ( max_reachable < reachable )
max_reachable = reachable;
}
return true;