Java 2ms, greedy and two pointers


  • 1
    K
    //          *           *          pre_max   cur_max          
    //    2, 0, 8, 0, 3, 4, 7, 5, 6, 1, 0 | 0, 5, 9 | 7 | 5,3,6  
    //                            *                  how_far
    // We don't need to add jumps at "6" because it's within pre_max(max distance of "8")
        
        public int jump(int[] nums) {
            if (nums.length == 1)
                return 0;
            int jumps = 1;
            int target = nums.length - 1;
            int maxFar = nums[0]; // current max distance
            if (maxFar >= target)
                return jumps;
            int preMaxFar = 0; // previous max distance
            int howFar; // how far we can get at current index
            for (int i = 1; i < nums.length; i++) {
                howFar = i + nums[i];
                if (howFar > maxFar) {
                    // if index is within range of previous max distance, no need to jump
                    // else jump and update previous max distance
                    if (i > preMaxFar) {
                        ++jumps;
                        preMaxFar = maxFar;
                    }
                    maxFar = howFar; // always update current max distance
                    if (maxFar >= target) { // Reach target, return
                        return jumps;
                    }
                }
            }
            return  jumps;
        }

Log in to reply
 

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