O(n) solution, still being judged as slow (updated with an accepted solution)


  • 0
    L

    The code use a dictionary to record whether it can jump to the end from certain index. In the outer loop, the index is scanned in decreasing order. And the inner loop is used to test that index with all possible jumps. Although it passed couples of test on my PC, I got to speed it up with other strategy.

    class Solution:
        # @param A, a list of integers
        # @return a boolean
        def canJump(self, A):
            ii,dict=len(A)-2,{len(A)-1:True if A[-1]>0 else False}
            while ii>=0:
                jj,dict[ii]=1,False
                while jj<=A[ii]:
                    # stop the loop if the index is out the range of the array
                    if not dict.has_key(ii+jj):
                        break
                    elif dict[ii+jj]==True:
                        dict[ii]=True
                        break
                    jj+=1
                ii-=1
            return dict[0]
    

    [updated]
    the updated code run through each index and determine the furthest steps (maxMove) we can make at that index. It this number is zero, that means the index cannot be jump through. Then return False. Also if the maximum steps can reach the end of the array, stop the iterations and return True.

    class Solution:
        # @param A, a list of integers
        # @return a boolean
        def canJump(self, A):
            maxMove,res=0,True
            for ii in range(1,len(A)):
                maxMove=max(A[ii-1],maxMove-1)
                if maxMove==0:
                    res=False
                    break
                if (maxMove+ii-1>=len(A)-1):
                    break
            return res

Log in to reply
 

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