[LeetCode] 55. Jump Game
Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Determine if you are able to reach the last index.
For example:
A =
A =
[2,3,1,1,4]
, return true
.
A =
[3,2,1,0,4]
, return false
.
Thought process:
- Sub-problem: if you are able to reach any index.
- Formula: f[i] = (f[0] && 0 + jump[0] >= i) || (f[1] && 1 + jump[1] >= i) || . . . || (f[i - 1] && i - 1 + jump[i - 1] >= i).
- Initialization: f[0] = true.
- Answer: f[last index].
Solution 1:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | public class Solution { public boolean canJump(int[] nums) { int length = nums.length; boolean[] f = new boolean[length]; f[0] = true; for (int i = 1; i < length; i++) { for (int j = 0; j < i; j++) { if (f[j] && j + nums[j] >= i) { f[i] = true; break; } } } return f[length - 1]; } } |
Time complexity: O(n^2).
Unfortunately, this solution exceeds the time limit, because there's a O(n) greedy solution.
The idea is to iterate through the array starting from the end of it. As soon as we find a point that can jump to our current index, we move to that point. This solution relies on the logic that, if there are multiple points that can jump to the last index, it is always safe to move the the closest index to the last index, because farther indexes can jump to the closest index for sure.
Solution 2:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | public class Solution { public boolean canJump(int[] nums) { int length = nums.length; int last = length - 1; for (int i = length - 2; i >= 0; i--) { if (i + nums[i] >= last) { last = i; } } return last == 0; } } |
Time complexity: O(n).
Comments
Post a Comment