# Python Greedy & BFS Solution

• ### Greedy Solution(Accepted, 56 ms):

``````class Solution(object):
def canJump(self, nums):
n=len(nums)-1
jump=n
for i in xrange(n-1,-1,-1):
if i+nums[i]>=n or i+nums[i]>=jump:
jump=i # jump is the lowest index that has path(s) to last index
return jump==0 or i+nums[i]>=n
``````

### BFS Solution(Time Limit Exceeded, but idea is right):

``````class Solution(object):
def canJump(self, nums):
if len(nums)==1:
return True
box=[[0,nums[0]]] # box keeps nodes that can be jumped to
i=0
while 1:
if i==len(box):
break
# add left node to box
left=box[i][0]-box[i][1]
for e in xrange(max(left,1),i):
if [e,nums[e]] not in box:
box.append([e,nums[e]])
# add right node to box
right=box[i][0]+box[i][1]
if right>=len(nums)-1: # return True if a node can reach the last index
return True
else:
for e in xrange(i+1,right+1):
if [e,nums[e]] not in box:
box.append([e,nums[e]])
i+=1
return False # if no node in the box can reach the last index``````

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