• I think the asymptotic running time of my python code is O(n), however, it runs very slow. The function canJump() comes from Jump Game I which I passed. The actual running time for Jump Game I for 25000 descending test case is 6 milliseconds on my iMac, but the Jump Game II code, which I believe is also O(n) takes 117 milliseconds for only 2500 descending test case.

I am not sure what goes wrong here, please someone help me to diagnose the issue in my code. Thanks a ton.

``````class Solution:
# @param A, a list of integers
# @return an integer
def jump(self, A):
""" The idea is to iterate from A[-1] to A[0] and calculate the minimum jumps to reach the end and then put that result back to A[i]. Bottom-up memoized approach.
Denote digit = A[i]
1. if digit == 0: no way to reach the end, so we put len(A) here becuse the maximum jumps from A[1] to the end is len(A) - 1
2. if digit >= distance from i to the end, we only need 1 jump. And distance from i to the end is (len(A) - i - 1)
3. else, we find the minimum jumps from the candicates where A[i] can jump to, take their minimum and plus 1.
"""
# first we validate we can definitely jump to the end, O(n)
if not self.canJump(A):
return 0
for index in xrange(len(A) - 2, -1, -1):
digit = A[index]
# 1
if digit == 0:
A[index] = len(A)
continue
# 2
if digit >= len(A) - index - 1:
A[index] = 1
else:
# 3
# the candidates starts from index + 1, and ends at either (index + A[index]) or (len(A) - 2) which one is smaller
next_index = min(index + digit + 1, len(A) - 1)
A[index] = min(A[index + 1:next_index]) + 1
return A[0]``````

• can somebody explain me how to optimize this code to run in linear time?

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