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