6 line java solution in O(n)


  • 48
    H

    The basic idea is this: at each step, we keep track of the furthest reachable index. The nature of the problem (eg. maximal jumps where you can hit a range of targets instead of singular jumps where you can only hit one target) is that for an index to be reachable, each of the previous indices have to be reachable.

    Hence, it suffices that we iterate over each index, and If we ever encounter an index that is not reachable, we abort and return false. By the end, we will have iterated to the last index. If the loop finishes, then the last index is reachable.

    public boolean canJump(int[] nums) {
        int reachable = 0;
        for (int i=0; i<nums.length; ++i) {
            if (i > reachable) return false;
            reachable = Math.max(reachable, i + nums[i]);
        }
        return true;
    }

  • 2
    W

    Nice solution!

    I have the same idea. My solution will only "walk in the reachable" to see if it can reach the last index.

    public class Solution {
        public boolean canJump(int[] nums) {
            int n = nums.length;
            if (n==0) return false;
            int max_reach = 0;
            boolean ret = false;
            for (int i=0;i<=max_reach;i++) {
                if (max_reach >= n-1) {
                    ret = true;
                    break;
                }
                int reach = i+nums[i];
                if (reach > max_reach) max_reach = reach;
                
            }
            return ret;
        }
    }

  • 0
    F

    can you explain a bit about why (i + nums[i])?


  • 0
    R

    reachableNew = i + nums[i] is the basic problem definition that from any index 'i' you can make a max jump of length nums[i]
    reachableNew = reachableOld e.g. if nums= [2,0,1], then at i=1. hope this helps


  • 0
    Y

    Very good solution, also thanks for the explanation, it's very clear.


  • 0
    C

    There is an very insteresting observation here. I used similar method. the only difference is to terminate the execution early once it is confirmed that it can reach the end:
    int canReach = 0;
    for(int i = 0; i < nums.length; i++){
    if( i > canReach) return false;
    // if(canReach >= nums.length - 1){
    // return true;
    // }
    canReach = canReach > i + nums[i] ? canReach: i + nums[i];
    }
    return true;

    BUt in fact, this extro if statement is makeing the program less performing. In some edge case, it is excuting too long.


  • 1
    J

    This is a greedy algorithm, right?


  • 0
    Z

    clear solution.


  • 0
    W

    cool idea!!!!


  • 0
    C

    Oh my god, this is amazing!!


  • 0
    W

    code master!!!!!!!!!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.