[Leetcode] Problem Series of Jump Game

By Long Luo

This article is the solution Leetcode Jump Game Problems Series.

1. 55. Jump Game

55. Jump Game

Brute Force

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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

45. Jump Game II

DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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

1306. Jump Game III

BFS

BFS Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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

1345. Jump Game IV

BFS

1

Analysis

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

5. 1340. Jump Game V

1340. Jump Game V

1

Analysis

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

6. 1696. Jump Game VI

1696. Jump Game VI

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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

1871. Jump Game VII

1

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.