My O(n) time O(1) space Solution.


  • 0
    U

    Only one pass. O(n) time O(1) memory.

    public class Solution {

    public int jump(int[] A) {
        if (A == null || A.length <= 1) {
            return 0;
        }
        
        int tail = A[0];
        int min = 1;
        int begin = 0;
        while (tail < A.length - 1) {
            int maxPace = 0;
            for (int i = begin ; i <= tail; i++) {
                maxPace = Math.max(maxPace, i + A[i]);
            }
            begin = tail + 1;
            tail = Math.max(tail, maxPace);
            min++;
        }
        return min;
    }
    

    }


  • 0
    N

    Sorry, this is a very nice and neat solution!!


  • 0
    P

    Why do set
    begin = tail + 1
    before
    tail = Math.max(tail, maxPace)?


  • 0
    T

    Max(tail,maxPace) is not necessary, just set tail=maxPace


  • 0
    T

    I kind of like starting from 0 instead of 1, sort of less looking like less "edge cases"

      public class Solution {
    public int jump(int[] A) {
        if (A == null   ) return 0;
            int begin = 0;
            int tail = 0;
            int steps = 0;
            while(tail < A.length-1) {
                int maxPace = 0;
                for(int i=begin;i<=tail;i++) {
                    maxPace = Math.max(maxPace, i+A[i]);
                }
                begin = tail +1;
                tail = maxPace; // this means we walked one more step
                steps ++;
            }
            
            return steps;
        }
    }
    

Log in to reply
 

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