Sharing My AC Java Solution


  • 37
    Z

    Hi All, below is my AC solution:

    public int jump(int[] A) {
        int maxReach = A[0];
        int edge = 0;
        int minstep = 0;
        
        for(int i = 1; i < A.length; i++) {
            if (i > edge) {
                minstep += 1;
                edge = maxReach;
                if(edge > A.length - 1)
                    return minstep;
            }
            maxReach = Math.max(maxReach, A[i] + i);
            if (maxReach == i):
                return -1;
        }
        
        return minstep;
    } 
    

    When iterate the array, I set an edge for the Search phase, which means that if I exceeds the edge, the minstep must add one and the maxReach will be update. And when the last index is within the range of the edge, output the minstep.

    [2, 3, 1, 1, 4]

    First, the edge is 0;
    Second, after start iterate the array, it exceeds the edge 0 when reaching the A[0] and update the edge to 2;
    Third, after it reach the A[2], it exceeds the edge 2 and update the new edge to the maxReach 4.
    Finally, end of the array is inside the edge, output the minstep.


  • 0
    Y

    You did not check the case in which it cannot reach the end


  • 23
    T

    To check if the end can be reached, modify the last line:

    public int jump(int[] A) {
        int count = 0, max = 0;
        for (int i = 0, nextMax = 0; i <= max && i < A.length - 1; i++) {
            nextMax = Math.max(nextMax, i + A[i]);
            if (i == max) {
                max = nextMax;
                count++;
            }
        }
        // if there is no way to get to the end, return -1
        return max >= A.length - 1 ? count : -1;
    }

  • 0
    Z

    You are right, Thank you so much for pointing out.


  • 0
    Z

    Good, thank you for your solution.


  • 0
    L

    try this: if the given array is [2,0,0,0], it will stuck and never return.


  • 0
    X

    in the note of this question: "You can assume that you can always reach the last index." But it is indeed a nice try anyway:). Thanks for sharing.


  • 0
    X

    @XindiWang You shouldn't assume it in a real interview. You should always consider all corners cases.


  • 0
    A

    said in Sharing My AC Java Solution:

    maxReach

    thanks for the solution but seems in line if (maxReach == i): it should be if (maxReach < i)


  • 1
    O

    I don't understand this sentence

    if(maxReach==i) return -1;
    

    I add this sentence ,it has a problem
    0_1471515545413_upload-2c00f9e3-2846-4dfd-a271-439ce05ec0b6
    But I remove it, it accepted.
    0_1471515605839_upload-4910b39b-a364-4512-bb54-3c9853e511fb


  • 0
    A

    @owen1190 maxReach is supposed to be always larger than i after the ith iteration. If they are the same, it means we encounter cases like [2,0,0,0,0] which the last element cannot be reached. Then, change edge > nums.length - 1to be edge >= nums.length - 1, the code will be accepted.


Log in to reply
 

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