Please help with TLE issue


  • 1
    I

    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]

  • 0
    A

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


Log in to reply
 

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