-
Notifications
You must be signed in to change notification settings - Fork 0
/
0055--jump-game.js
41 lines (34 loc) · 1.58 KB
/
0055--jump-game.js
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
33
34
35
36
37
38
39
40
41
// 55. Jump Game
// You are given an integer array nums. You are initially positioned at the array's first index, and each element in the array represents your maximum jump length at that position.
// Return true if you can reach the last index, or false otherwise.
// Input: nums = [2,3,1,1,4]
// Output: true
// Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.
// Input: nums = [3,2,1,0,4]
// Output: false
// Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.
// Constraints:
// 1 <= nums.length <= 104
// 0 <= nums[i] <= 105
function canJump(nums) {
// initially assume all nums are not reachable
const reachables = new Array(nums.length).fill(false);
// as it's always possible to jump to the first number in the array, first item is reachable
reachables[0] = true;
// in order to check if the num at index i is reachable
// check for each of its preceding nums
// --- whether preceding num j is reachable (reachables[j] &&)
// --- whether the sum of its maximum jump length and index can cover i length (j + nums[j] >= i)
// if these two conditions are met, num at index i is reachable (reachables[i] = true)
// break the inner loop and check if the next number is reachable
for (let i = 1; i < nums.length; i++) {
for (let j = 0; j < i; j++) {
if (reachables[j] && j + nums[j] >= i) {
reachables[i] = true;
break;
}
}
}
// after the loop, return whether last num is reachable
return reachables[reachables.length - 1];
}