# Sharing my accepted Python code.

• I think the runtime should be O(N) and space complexity is O(1).

``````def jump(self, A):
if len(A) <= 1:
return 0
end = 0 + A[0]
start = 0
step = 1
maxDis = 0 + A[0]
while end < len(A)-1:
for i in range(start+1, end+1):
maxDis = max(maxDis, A[i]+i)
start = end
end = maxDis
step += 1

return step``````

• This is excellent. I used the same strategy but yours saved some checking that I did not realize was redundant.

def jump(self, A):

``````if len(A)==0:
return 0
i=0
steps=0
while i+A[i]+1<len(A):
maxReach=0
for j in xrange (i+1, i+A[i]+1):
if j+A[j]>maxReach:
maxReach=j+A[j]
maxSecond=j
i=maxSecond
steps=steps+1
return steps if i+1==len(A) else steps+1
``````

• Nice job! :)

• Great solution, below is my rewrite so that no need to explicitly handle the edge case:

``````def jump(self, A):
jumps = 0
start = end = max_reach = 0
while max_reach < len(A) - 1:
for i in range(start, end + 1):
max_reach = max(max_reach, i + A[i])
start, end = end + 1, max_reach
jumps += 1
return jumps``````

• nice and neat solution.

• Great solution! I have a question about it, anyone know if this is a DP method or Greedy method? I'm a little confused about these two. Thanks.

• @lei69 I wish I can categorize it into DP or greedy. But however, it looks more like a BFS solution. This question is one good example that the best solution for a optimality problem is not always DP.

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