Is there better solution for Jump Game II?


  • 6
    C

    my solution exceeds time limit.
    I use an array to track the min step at i . It seems my solution is not efficient enough. You guys have better solution?

    class Solution {
    public:
        int jump(int A[], int n) {
            vector<int> track(n, 0);
            
            for(int i=1; i<n; i++){
                int min = INT_MAX;
                for(int j=0; j<i; j++){
                    if(track[j] < min && A[j]+j >= i)
                        min = track[j];
                }
                track[i] = min+1;
            }
            return track[n-1];
        }
    };

  • 1
    P
    // Top-down DP
    
    class Solution {
        vector<int> opt;
    public:
        int jump(int A[], int n) {
            opt.assign(n, -1);
            // set destination to be immediately available (0 step)
            opt[n - 1] = 0;
            return helper(A, n, 0);
        }
        
        int helper(int A[], int n, int index) {
            if (opt[index] == -1) {
                // max position we can reach jumping from index
                int max_pos = index + A[index];
                // one step to reach destination
                if (max_pos >= n - 1) opt[index] = 1;
                else { // DP
                    for (int i = index + 1; i <= index + A[index]; i++) {
                        // Optimization: test if jump from start takes fewer steps
                        if (i + A[i] <= max_pos) continue;
                        int steps = helper(A, n, i);
                        if (steps != -1 && (opt[index] == -1 || steps + 1 < opt[index]))
                            opt[index] = steps + 1;
                    }
                }
            }
            return opt[index];
        }
    };

  • 0
    S

    Hi pengqun, appreciate your code with comments, if you can describe your thought in some words, it would be better. Thx!


  • 0
    M

    Here is my solution. It fails a test on the online judge but the same test passes with the correct results on my Linux box running openjdk 7. Not sure whats up. Anyway it uses recursion with memorisation to prevent recalculating sub trees that have been visited already.

    public HashMap<Integer, Integer> map;
    private boolean stop = false;
    
    public int jump(int[] A) {
        if (A.length == 0) {
            return 0;
        }
        if (A.length == 1 && A[0] != 0) {
            return 0;
        }
        map = new HashMap<Integer, Integer>();
        return recurse(0, 0, A);
    
    }
    
    public int recurse(int current, int hops, int[] A) {
        int min = Integer.MAX_VALUE;
        if (stop) {
            return min;
        }
        int maxNewHops = A[current];
        if (current + maxNewHops >= A.length - 1) {
            if (maxNewHops > 0) {
                return hops + 1;
            } else {
                return hops;
            }
        }
        hops++;
        for (int i = 1; i <= maxNewHops; i++) {
            if (stop){
                break;
            }            
            int result = 0;
            if (map.get(current + i) == null) {
                result = recurse(current + i, hops, A);
                map.put(current + i, result - hops);
            } else {
                result = hops + map.get(current + i);
            }
            min = Math.min(min,result);
            if (min <= 2) {
                stop = true;
            }
        }
    
        return min;
    }

  • 0
    P

    you should ask your question in a new post. And this question can be solved in O(N) without recursion


  • 0
    M

    thanks for the tip. Will take a look. Is there anywhere we can see other solutions once we have successfully submitted an answer?


  • 77
    C

    Here is a solution from other.

    /*
     * We use "last" to keep track of the maximum distance that has been reached
     * by using the minimum steps "ret", whereas "curr" is the maximum distance
     * that can be reached by using "ret+1" steps. Thus,
     * curr = max(i+A[i]) where 0 <= i <= last.
     */
    class Solution {
    public:
        int jump(int A[], int n) {
            int ret = 0;
            int last = 0;
            int curr = 0;
            for (int i = 0; i < n; ++i) {
                if (i > last) {
                    last = curr;
                    ++ret;
                }
                curr = max(curr, i+A[i]);
            }
    
            return ret;
        }
    };

  • 0
    P

    I don't think you can see others' solutions after your answer is accepted. But if you feel that your answer is not right/efficient enough, you can always post a new question. The solution from chentao169 is O(N) and you should look at that.


  • 0
    A

    Hello,
    you said that, your solution fails on the online judge but passes on you own machine.
    It might be a good idea to try to initialize your stop variable inside your jump method.
    There is a problem with global variables in the online judge system.


  • 0

    @mxc You must reinitialize all member data variables, as the same Solution instance is reused for each test case.


  • 0
    S
    This post is deleted!

  • 0
    T
    class Solution {
    public:
        int jump(int A[], int n) {
            // Note: The Solution object is instantiated only once and is reused by each test case.
            if(n == 1)return 0;
            int canArrive = 0, res = 0, lastCanArrive = 0;
            for(int i = 0; canArrive < n-1; i++)
                 if(i + A[i] > canArrive)
                 {
                     if(i > lastCanArrive)
                     {
                         res++;
                         lastCanArrive = canArrive;
                     }
                     canArrive = i + A[i];
                 }
            return res+1;
        }
    };

  • 0
    S

    Hi @tenos, thanks for your sharing. Could you please try to add some words about your algorithm or comments in code? It would be more helpful for others.


  • 9
    G
    int jump(int A[], int n) {
        int min_stp = 0, lng_dst = 0, i = 0, nxt_dst = 0;
        while(lng_dst < n - 1){
            for(; i <= lng_dst; i++)
                if(i + A[i] > nxt_dst) nxt_dst = i + A[i];
            if(nxt_dst > lng_dst){
                lng_dst = nxt_dst;
                min_stp++;
            } else return -1;
        }
        return min_stp;
    }
    

    The for-loop inside the while-loop iteratively count the longest distance reachable in current step. Then take the longest reachable one in current region as the next bounding edge of the next iteration. Also i catch the unreachable case that returns -1. It's gonna take O(n) to get done.


  • 0
    R

    I think your solution has a assumption that when you reach the max distance by ret steps, the position can always move further.

    It will fail on such data: [3, 2, 1, 0, 4] which can't reach the final one.

    I modified your solution as this:

    class Solution:
        # @param A, a list of integers
        # @return an integer
        def jump(self, A):
            ret = 0
            last = 0
            curr = 0
            for i in range(len(A)):
                if i > last:
                    # if not last one and can't go further
                    if (curr == last) and (last < len(A)-1):
                        return -1   # never reach the last one
                    last = curr
                    ret += 1
                curr = max(curr, i+A[i])
            return ret
    

  • 0
    8

    you are right!


  • 0
    S

    your code gets fail for
    input A[10] = {4,5,6,2,0,0,0,0,0,0};


  • 0
    R

    Here is my solution which is accepted in OJ. The basic idea is in the current step to predict the maximum distance in the next step within the reach range based on the value A[start].

     public int jump(int[] A) {
        if(A==null || A.length<=1) return 0;
        return jump(A, 0, 0);
    }
    
    private int jump(int[] A, int start, int step){
        if(A[start]+start>=A.length-1) return step+1;
        
        int maxDist = -1;
        int index = 0;
        for(int i=A[start]; i>=1; i--){
            if(A[i+start]==0) continue;
            if(A[i+start]+start+i>maxDist) {
                maxDist=A[i+start]+start+i;
                index = i;
            }
        }
        
        if(maxDist<=0) return 0;
        
        return jump(A, start+index, step+1);
    }

  • 6
    S

    I'll throw in my two cents here. I believe my code is similar to others' in essence. However, I interpret my method as a simplified version of LEVEL-ORDER traversal, where the ith level contains the nodes that can be reached in as few as i steps (so if a node can be reached in, say, i, i+1 or i+2 steps, it should be included only in the ith level). As soon as we find that the last node appears in the current level, then the index of this level can be returned as the minimum number of jumps that is required to reach the last node.

    The implementation is actually simpler than a regular level-order travesal: All the values are already stored in an array, so there is no need to maintain an extra queue. We only need to maintain two pointers: 'lo' and 'hi', representing the start and end of the queue, respectively. We process the 'top' element (i.e. 'lo') one at a time, and add its possible children on the next level to the end of the 'queue' by expanding 'hi'. When we detect that 'lo' is greater than the original 'hi'. it means that we have finished the current level, then we add one to the level index ('njump' in my code), and proceed to the next level.

    To expand the queue, we do not need to know which values are the children of the 'lo'
    element exactly, we only care about what the queue would look like after its children are 'pushed' to the end. That is, the elements that can be reached from 'lo' with ONE jump ( < A[lo] + lo) AND has not been visited ( > hi). Therefore, the end of the queue after the expansion should be:

    hi = max(hi, A[lo] + lo)
    

    The following code is slightly more verbose than the most concise implementations previously posted, but I believe it better illustrates my interpretation of this problem.

    int jump(int A[], int n) {
        int lo = 0, hi = 0;
        int njumps = 0;
        
        // Break from the loop as soon as we find that the last node is included in the queue
        while (hi < n - 1)  
        {
            int cur_hi = hi;
            while (lo <= cur_hi) // Process the current level.
            {
                hi = max(hi, A[lo] + lo); // Expand the current queue.
                lo ++; // Get ready to process the next element
            }
            njumps++; // Increase level index after a level is processed
        }
        return njumps;
    }
    

    This code, of course, does not consider the case when the last node cannot be reached (e.g. '[3 2 1 0 4]'), but it can be trivially modified to handle this case: If in a certain iteration, the 'queue' becomes empty ('lo == hi', indicating the traversal is completed), but we still have not reached the last node. It means the last node simply cannot be reached. We can do whatever error handling we would like to when this happens.
    Thus, this idea can also be applied to 'Jump Game I'. Only in that case, we don't even need to use LEVEL-ORDER travesal; a simple BFS would suffice.


  • 1
    W

    This is my solution accepted by OJ. I reused the existing array. A[i] means the minimum steps from pos i to pos n-1. The key idea is if A[i] > A[i - 1], pos i will never be the intermediate pos in the final path, so just make pos i 'adjacent' to pos i-1.

    class Solution {
    public:
        int jump(int A[], int n) {
            A[n - 1] = 0;
            for (int i = n - 2; i >= 0; i--) {
                int m = min(i + A[i], n - 1);
                A[i] = m == i ? n : A[m] + 1;
                for(int j = i + 1; A[j] > A[i]; j++) A[j] = A[i];
            }
            return A[0] >= n ? -1 : A[0];
        }
    };

Log in to reply
 

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