Jump Game

Description

https://leetcode.com/problems/jump-game/description/

Brutal Solution

Traverse from the start node, mark its range as true, then we can check the end of the list when traversion finished.

class Solution {
    public boolean canJump(int[] nums) {
        int size = nums.length;
        boolean[] mark = new boolean[size];
        for(int index = 0; index < size; index++) mark[index] = false;
        mark[0] = true;
        for(int index = 0; index < size; index++) {
            if(mark[index] == true) {
                int range = nums[index];
                if (range > 0) {
                    for (int i = 1; i <= range && i + index < size; i++) 
                        mark[index + i] = true;
                }
            } 
        }
        return mark[size - 1];
    }
}

Mark-Free Solution

In the solution above, we found some redundant traversion in the nested loop, to improve it, we should skip the meaningless procedure. To clarify how it works, we should introduce a pre-rule discovered by the fact:

If the item A is reachable, then the item before A must be reachable.

Then we use a varialbe rightIndex to record the reachable boundary in the right.

class Solution {
    public boolean canJump(int[] nums) {
        int size = nums.length;
        int rightIndex = 0;
        for(int index = 0; index < size; index++) {
            if(index <= rightIndex) {
                rightIndex = Math.max(rightIndex, nums[index] + index);
            } 
        }
        return rightIndex >= size - 1;
    }
}

Trimmed Solution

In the solution above, the procedure need to traverse all node regardless of the dataset. In fact we can terminate the result once we reached the end item of liste(success), or the current index is bigger than the rightIndex (fail)

class Solution {
    public boolean canJump(int[] nums) {
        int size = nums.length;
        int rightIndex = 0;
        for(int index = 0; index < size; index++) {
            if(index > rightIndex || rightIndex >= size - 1) break;
            rightIndex = Math.max(rightIndex, nums[index] + index); 
        }
        return rightIndex >= size - 1;
    }
}