Sharing my straightforward C++ solution


  • 20
    Z
    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.


  • 0
    T

    Really smart. Very excellent example of using greedy strategy.


  • 0
    Z

    Thanks a lot!!


  • 0
    W

    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?


  • 0
    Z

    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!


  • 0
    N
    This post is deleted!

  • -1
    N

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


  • 0
    A

    it does not solve the problem mentioned by Bluefeather


Log in to reply
 

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