/ Data Structure and Algorithms  

Leetcode 55. Jump Game

Question



Jump from the 0th index of the array, the distance of the jump is less than or equal to the corresponding number in the array. Determine if can reach the last index.

Similar Questions

Solution

We need to know from i-th position, what is the furthest position it can reach. If any of the element has a furthest position that can reach end, then return true. If reach is position that can’t be reached from previous elements, then return false.

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
if (nums.length == 1) {
    return true;
}

// the furthest postion that can reach
int furthest = 0;
// index of current position
int index = 0;

while (index < nums.length) {
    // the furthest postion can be reached from this index
    furthest = Math.max(furthest, nums[index] + index);

    index++;

    // if this postion can't be reached
    if (index > furthest) {
        return false;
    }

    // can reach last index
    if (furthest >= nums.length - 1) {
        return true;
    }
}

return true;