[Leetcode] Problem Series of Jump Game

By Long Luo

This article is the solution Leetcode Jump Game Problems Series.

1.

55. Jump Game

Brute Force

public boolean canJump(int[] nums) {
    int len = nums.length;
    boolean[] visited = new boolean[len];
    visited[0] = true;
    for (int i = 0; i < len; i++) {
        int steps = nums[i];
        if (visited[i] && steps > 0) {
            for (int j = 1; j <= steps && i + j < len; j++) {
                visited[i + j] = true;
            }
        }
    }

    return visited[len - 1];
}

Analysis

• Time Complexity: $O(n^2)$
• Space Complexity: $O(n)$

Greedy

Jump to the farest postion.

public boolean canJump(int[] nums) {
    int len = nums.length;
    int maxIdx = 0;
    for (int i = 0; i < len; i++) {
        int steps = nums[i];
        if (maxIdx >= i) {
            maxIdx = Math.max(maxIdx, i + steps);
            if (maxIdx >= len - 1) {
                return true;
            }
        }
    }

    return false;
}

Analysis

• Time Complexity: $O(n)$
• Space Complexity: $O(1)$

2.

45. Jump Game II

DP

public static int jump_dp(int[] nums) {
    int len = nums.length;
    if (len <= 1) {
        return 0;
    }

    int[] dp = new int[len];
    Arrays.fill(dp, Integer.MAX_VALUE);
    dp[0] = 0;
    int minStep = Integer.MAX_VALUE;
    for (int i = 0; i < len; i++) {
        int num = nums[i];
        for (int j = 1; j <= num && i + j < len; j++) {
            dp[i + j] = Math.min(dp[i + j], dp[i] + 1);
            if (i + j >= len - 1) {
                minStep = Math.min(minStep, dp[i] + 1);
                return minStep;
            }
        }
    }

    return minStep;
}

Analysis

• Time Complexity: $O(n^2)$
• Space Complexity: $O(n)$

Greedy

public int jump(int[] nums) {
    int maxPosition = 0;
    int end = 0;
    int steps = 0;
    for (int i = 0; i < nums.length - 1; i++) {
        maxPosition = Math.max(maxPosition, i + nums[i]);
        if (i == end) {
            end = maxPosition;
            steps++;
        }
    }

    return steps;
}

Think reverse, from destination to origin position.

public int jump(int[] nums) {
    int ans = 0;
    int position = nums.length - 1;
    while (position > 0) {
        for (int i = 0; i < position; i++) {
            if (i + nums[i] >= position) {
                ans++;
                position = i;
                break;
            }
        }
    }

    return ans;
}

Analysis

• Time Complexity: $O(n)$
• Space Complexity: $O(1)$

3.

1306. Jump Game III

BFS

BFS Solution:

public boolean canReach_bfs_opt(int[] arr, int start) {
    if (arr[start] == 0) {
        return true;
    }

    int len = arr.length;
    boolean[] visited = new boolean[len];
    Queue<Integer> queue = new LinkedList<>();
    queue.offer(start);
    visited[start] = true;

    while (!queue.isEmpty()) {
        int curPos = queue.poll();
        if (arr[curPos] == 0) {
            return true;
        }

        int right = curPos + arr[curPos];
        if (right >= 0 && right < len && !visited[right]) {
            visited[right] = true;
            queue.offer(right);
        }

        int left = curPos - arr[curPos];
        if (left >= 0 && left < len && !visited[left]) {
            visited[left] = true;
            queue.offer(left);
        }
    }

    return false;
}

Analysis

• Time Complexity: $O(n)$
• Space Complexity: $O(n)$

DFS

public boolean canReach_dfs(int[] arr, int start) {
    int len = arr.length;
    boolean[] vis = new boolean[len];
    return dfs(arr, vis, start);
}

public boolean dfs(int[] arr, boolean[] vis, int start) {
    if (start < 0 || start >= arr.length || vis[start]) {
        return false;
    }

    vis[start] = true;
    if (arr[start] == 0) {
        return true;
    }

    return dfs(arr, vis, start - arr[start]) || dfs(arr, vis, start + arr[start]);
}

Analysis

• Time Complexity: $O(n)$
• Space Complexity: $O(n)$

4.

1345. Jump Game IV

BFS

Analysis

• Time Complexity: $O(n)$
• Space Complexity: $O(n)$

5.

1340. Jump Game V

Analysis

• Time Complexity: $O(n)$
• Space Complexity: $O(n)$

6.

1696. Jump Game VI

public static boolean canJump(int[] nums) {
    int len = nums.length;
    int maxIdx = 0;
    for (int i = 0; i < len; i++) {
        int steps = nums[i];
        if (maxIdx >= i) {
            maxIdx = Math.max(maxIdx, i + steps);
            if (maxIdx >= len - 1) {
                return true;
            }
        }
    }

    return false;
}

Analysis

• Time Complexity: $O(n)$
• Space Complexity: $O(n)$

7.

1871. Jump Game VII

Analysis

• Time Complexity: $O(n)$
• Space Complexity: $O(n)$

---

All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote?? if you like?? it. Thank you:-)

Explore More Leetcode Solutions.