By Long Luo
This article is the solution Leetcode Jump Game Problems Series.
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(n2)
- 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)
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(n2)
- 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)
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)
1345. Jump Game IV
BFS
Analysis
- Time Complexity: O(n)
- Space Complexity: O(n)
1340. Jump Game V
Analysis
- Time Complexity: O(n)
- Space Complexity: O(n)
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)
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.