45. Jump Game II

LeetCode
,

Backtracking

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    int result = Integer.MAX_VALUE;
    List<Integer> path = new ArrayList<>();
    public int jump(int[] nums) {
        int n = nums.length;
        backtracking(nums, 0, n, 0);
        return result;
    }

    private void backtracking(int[] nums, int index, int max, int count) {
        if (index >= max) return;
        if (index == max - 1) {
            result = Math.min(result, count);
            return;
        }

        for (int i = index + 1; i <= Math.min(index + nums[index], max - 1); i++)
            backtracking(nums, i, max, count + 1);

    }
}

Remarks:

  1. TC: $O(k^n)$, n is the length of the array and k is the max value of nums[i]. -> Time Limit Exceeded

Greedy

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int jump(int[] nums) {
        int steps = 0;
        int end = 0;
        int farthest = 0;

        // only check until the last index
        for (int i = 0; i < nums.length - 1; i++) {
            farthest = Math.max(farthest, i + nums[i]);

            // when we each the current maximun (furthest) index, we need to jump
            if (i == end) {
                steps++;
                end = farthest;
            }
        }
        return steps;
    }
}

Remarks:

  1. TC: $O(n)$, SC: $O(1)$
  2. Premise in the requirements: The test cases are generated such that you can reach nums[n - 1]., so we don’t care if the path can reach the end or not. What we only care is how far we can reach with less steps.