O(1) space, but used more time, why?


  • 0
    M

    If you imagine P[i][j] as: the max length of common subarray end with A[i] and B[j], then you will get a matrix for P[][].
    And I found that, if you walk through this matrix across the diagonal line each time, you will be able to use only 1 var to store P[i-1][j-1] each time. So you don't need an array !
    But after I changed my code in the way above, the runtime is longer than before. I can't figure out the reason, since I still walk through each P[i][j] once to get the answer.

    My code is shown below:

    class Solution(object):
        def findLength(self, A, B):
            """
            :type A: List[int]
            :type B: List[int]
            :rtype: int
            """
            # O(1) space
            # O(m*n) time
            lA, lB = len(A), len(B)
            maxP = 0
    
            # traverse the upper diagonal
            for j in range(lB):
                P = 0
                i = 0
                while i < lA and j < lB:
                    if A[i] == B[j]:
                        P = P + 1
                    else:
                        P = 0
                    maxP = max(P, maxP)
                    i += 1
                    j += 1
    
            # traverse the lower diagonal
            for i in range(lA):
                P = 0
                j = 0
                while i < lA and j < lB:
                    if A[i] == B[j]:
                        P = P + 1
                    else:
                        P = 0
                    maxP = max(P, maxP)
                    i += 1
                    j += 1
    
            return maxP

Log in to reply
 

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