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

• 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``````

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