Python O(n) Time & O(n) Space - Beat 100%


  • 0
    X

    The key to get O(n) time complexity other than O(nB) is to find the next jump with a O(1) operation.

        def cheapestJump(self, A, B):
            """
            :type A: List[int]
            :type B: int
            :rtype: List[int]
            """
            if A[-1] == -1: return []
            dp = [None] * len(A)
            dp[-1] = (A[-1], len(A))
            window = collections.deque()
            window.append((A[-1], len(A)-1))
            i = len(A) - 2
            while i >= 0:
                if not window: break
                if A[i] != -1:
                    cost = A[i] + window[-1][0]
                    to = window[-1][1]
                    dp[i] = (cost, to)
                    while window and window[0][0] >= cost:
                        window.popleft()
                    window.appendleft((cost, i))
                if i + B == window[-1][1]:
                    window.pop()
                i -= 1
            if not dp[0]:
                return []
            i = 0
            result = []
            while i != len(A):
                result.append(i + 1)
                i = dp[i][1]
            return result
    

Log in to reply
 

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