Fork me on GitHub

Jump Game II

Posted on

Description

https://leetcode.com/problems/jump-game-ii/description/

Naive Solution(TLE)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int jump(int[] nums) {
        int size = nums.length;
        if (size == 1) return 0;
        LinkedList<Integer> queue = new LinkedList<Integer>();
        queue.add(0);
        int steps = 1;
        while (queue.isEmpty() == false) {
            LinkedList<Integer> tempQueue = new LinkedList<>(queue);
            queue = new LinkedList<Integer>();
            while(tempQueue.isEmpty() == false) {
                int pos = tempQueue.pop();
                int range = nums[pos];
                if (pos + range >= size - 1) return steps;
                for(int i = 1; i <= range; i++) queue.add(pos + i);
            }
            steps += 1;
        }
        return -1;
    }
}

Button Up

We maintain the range of each depth, using leftBound and rightBound.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int jump(int[] nums) {
        if (nums == null) return 0;
        int size = nums.length;
        if (size == 0 || size == 1) return 0;

        int leftBound = 0, rightBound = 0;
        int currentStep = 0;
        int currentIndex = 0;
        while(rightBound < size - 1) {
            int oldRightBound = rightBound;
            currentIndex = leftBound;
            do {
                int range = nums[currentIndex];
                rightBound = Math.max(rightBound, currentIndex + range);
                currentIndex += 1;
            }while(currentIndex <= oldRightBound);
            if (rightBound <= oldRightBound) return -1; //Wrong answer
            leftBound = oldRightBound + 1;
            currentStep += 1;
        }
        return currentStep;
    }
}