Sharing my accepted Python code.


  • 4
    X

    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

  • 0
    C

    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
    

  • 0
    X

    Nice job! :)


  • 0
    C

    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

  • 0
    D

    nice and neat solution.


  • 0
    L

    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.


  • 0
    D

    @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.


Log in to reply
 

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