My accepted Java Solution


  • 3
    A

    Basically I used a ptr to keep track of the last index of position that we have finalized the minimum steps. For each position, the minimum steps will be set exactly once, so the run time is O(n).

     public int jump(int[] A) {
            int n = A.length;
            int[] minsteps = new int[n];
            int runner = 0;
            int ptr = 1;
            for (int i=0; i<n && ptr < n; i++) {
                int maxStep = A[i];
                int current = minsteps[i];
                if (maxStep + i < ptr) {
                    continue;
                }
                for (int j=ptr; j <= maxStep + i && j < n; j++) {
                    minsteps[j] = current + 1;
                }
                ptr = maxStep+i+1;
            }
            return minsteps[n-1];
        }

Log in to reply
 

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