O(mn) time O(1) space solution


  • 1
    I

    Intuitively, the algorithm slides one array over the other and for each sliding position compute the max length of repeated subarray within the overlapping window.

    class Solution(object):
        def findLength(self, A, B):
            B,A = sorted([A,B],key=len)
            m = len(A)
            n = len(B)
            maxLen = 0
            for a in xrange(-n+1,m+n-1):
                cnt = 0
                for ptrB in xrange(n):
                    ptrA = a+ptrB
                    if ptrA < 0 : continue
                    if ptrA >= m : break
                    if A[ptrA]==B[ptrB]:
                        cnt += 1
                        if cnt > maxLen: maxLen = cnt
                    else:
                        cnt = 0
            return maxLen
    

    Complexity: Let m>n, the outer loop runs for m+2n-1 (< 3m) times and the inner loop runs n times. So the time complexity is O(mn) and no extra space used.


Log in to reply
 

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