Sharing my straightforward C++ solution

• ``````int jump(int A[], int n) {
if(n == 0){
return 0;
}
int maxReachPos = A[0];
int curMaxReachPos = A[0];
int curStep = 1;
for(int i = 1; i <= min(n, maxReachPos); i++){
curMaxReachPos = max(curMaxReachPos, i + A[i]);
if(i == n - 1){
return curStep;
}
if(i == maxReachPos){
maxReachPos = curMaxReachPos;
curStep++;
}
}
return 0;
}
``````

The variable maxReachPos indicates the farthest reachable position and the variable curMaxReachPos indicates the current farthest reachable position.

At the very beginning, both maxReachPos and curMaxReachPos are equal to A[0].

In the For loop, we keep updating curMaxReachPos while i <= maxReachPos. However, if( i == n - 1), we return curStep, which is the minimum step. If i reaches the maxReachPos, we update maxReachPos with curMaxReachPos and increment curStep by one.

Finally, if we can't reach the end point, just return 0.

• Really smart. Very excellent example of using greedy strategy.

• Thanks a lot!!

• I have a question here. When `n = 1`, the code `curMaxReachPos = max(curMaxReachPos, i + A[i]);` will visit A[1]. It's not safe and correct, right?

• Thank you so much for your insight comment! You are right. So I have changed my code. I changed the For loop to for(int i = 1; i <= min(n, maxReachPos); i++). Thanks again!

• This post is deleted!

• 3Q for your solution. excellent,and much better than my solution which is O(n*n);

• it does not solve the problem mentioned by Bluefeather

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.