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 start = 0 step = 1 maxDis = 0 + A 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
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
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.