718 maximum length of repeated subarray.py

"""
Given two integer arrays `nums1` and `nums2`, return the maximum length of a
subarray that appears in both arrays.
"""

class Solution:
    def findLength_(self, nums1: list[int], nums2: list[int]) -> int:
        shorter, longer = sorted([nums1, nums2], key=len)
        l_max = 0
        for i in range(len(shorter)):
            for j in range(len(longer)):
                for l in range(min(len(shorter) - i, len(longer) - j)):
                    if shorter[i + l] != longer[j + l]:
                        l_max = max(l_max, l)
                        break
                else:
                    l_max = max(l_max, l + 1)
                if l_max >= len(longer) - j: break
            if l_max >= len(shorter) - i: break
        return l_max

# better solution
    def findLength(self, nums1, nums2):
        memo = [[0] * (len(nums2) + 1) for _ in range(len(nums1) + 1)]
        for i in range(len(nums1) - 1, -1, -1):
            for j in range(len(nums2) - 1, -1, -1):
                if nums1[i] == nums2[j]:
                    memo[i][j] = memo[i + 1][j + 1] + 1
        return max(max(row) for row in memo)


testcases = [
    {'input': ([1,2,3,2,1], [3,2,1,4,7]), 'result': 3},
    {'input': ([0,0,0,0,0], [0,0,0,0,0]), 'result': 5},
    {'input': ([0,0,0,0,1], [1,0,0,0,0]), 'result': 4},
    {'input': ([5,14,53,80,48], [50,47,3,80,83]), 'result': 1},
    {'input': (
        [16,96,0,94,91,50,21,6,29,49,56,36,3,41,0,56,31,30,48,39,31,41,54,58,4,62,46,54,1,78,47,12,88,53,55,24,22,62,69,81,55,98,12,95,68,27,16,51,25,0,6,86,87,87,11,92,88,74,5,8,19,73,20,44,64,15,97,52,4,32,11,32,46,32,35,47,48,23,94,12,57,59,15,16,30,42,67,36,12,99,99,37,52,50,66,51,73,83,11,21,20,16,97,78,90,0,10,18,15,17,86,13,94,82,51,97,95,33,90,97,68,43,92,55,60,76,54,93,61,21,80,52,69,81,80,60,26,13,59,23,38,66,78,63,5,6,38,92,3,8,98,30,45,31,56,80,0,57,28,24,6,5,80,81,45,90,2,24,71,44,8,49,42,32,96,41,20,52,82,16,58,90,58,65,38,28,26,9,75,35,55,17,74,59,75,99,65,96,45,41,39,27,72,87,92,51,62,37,13,14,32,16,41,8,8,94,19,93,74,92,86,44,33,3,27,32,21,28,18,81,5,6,30,92,79,56,88,5,43,44,60,42,48,50,4,97,8,16,75,27,72,49,1,25,3,83,58,69,85,55,32,60,74,23,56,14,40,51,59,40,56,50,55,32,82,92,85,96,37,58,79,39,26,19,68,23,51,99,77,23,65,43,12,59,4,95,73,91,50,60,66,4,73,0,16,58,35,92,29,89,61,77,80,35,15,71,83,11,69,77,97,22,0,73,42,51,25,32,92,14,26,81,89,89,75,3,69,71,12,43,89,78,71,19,24,49,0,95,48,66,67,38,26,60,20,80,32,7,42,83,75,22,60,25,75,44,55,55,76,60,14,31,2,76,0,58,53,15,57,13,89,96,36,26,17,65,20,42,32,62,62,1,74,29,24,63,74,75,23,34,60,13,94,7,85,75,13,91,97,90,95,51,60,23,11,25,92,18,29,12,50,16,43,45,61,17,42,51,3,8,97,7,5,79,30,41,61,70,32,30,84,42,78,19,63,88,26,99,3,97,48,1,24,13,11,19,5,26,76,56,72,82,63,29,86,44,62,24,21,61,10,25,46,66,88,72,14,68,64,98,30,0,79,45,86,45,99,9,84,81,17,41,50,80,70,85,73,52,9,23,92,56,89,58,34,4,57,82,69,73,82,28,55,55,16,82,55,90,97,32,58,91,53,55,1,62,50,99,12,33,31,42,46,40,88,33,56,74,79,18,81,7,58,33,11,35,33,69,5,96,32,73,79,68,42,35,40,41,8,10,85,83,61,88,63,27,86,14,8,7,4,94,88,74,36,98,16,75,39,33,57,90,44,53,74,34,21,11,74,95,54,7,89,54,98,66,92,82,32,61,4,33,5,9,59,68,34,90,35,47,40,53,42,63,44,95,65,96,60,13,71,76,39,69,97,97,11,49,4,91,48,93,87,99,66,44,93,11,64,94,66,92,62,79,77,36,1,40,0,96,33,89,79,70,66,50,41,2,43,41,69,36,48,65,45,52,78,2,10,85,47,70,4,88,73,55,15,58,89,98,96,40,72,14,69,2,14,74,27,64,83,68,75,50,73,42,55,3,24,17,18,56,5,10,68,56,56,59,56,94,74,80,81,77,83,29,90,90,22,96,62,98,62,65,43,4,74,88,33,76,24,73,52,31,22,82,34,76,65,99,97,32,66,71,49,3,35,72,15,27,82,43,37,91,79,46,89,96,58,50,99,15,50,50,35,81,10,52,97,57,3,1,59,5,97,10,8,18,10,56,84,7,31,29,90,65,77,55,61,37,57,21,32,17,87,98,23,86,68,36,11,89,62,21,6,36,65,87,22,62,87,96,13,82,3,72,52,64,26,72,74,86,88,53,90,34,72,27,29,72,50,53,32,16,75,72,65,5,17,9,42,99,16,0,8,51,7,59,36,44,43,20,87,60,91,31,28,7,56,75,13,9,47,80,9,9,86,12,1,2,19,42,62,61,19,41,72,10,48,41,95,95,84,43,94,98,95,29,59,67,17,32,86,96,71,24,49,76,31,78,45,8,12,95,70,94,21,41,65,57,81,89,77,35,71,44,58,99,38,24,42,16,55,68,91,35,33,94,9,99,41,39,84,26,42,46,63,16,19,42,69,77,36,14,91,89,67,79,60,39,6,14,7,72,32,50,1,21,24,17,83,16,81,42,88,70,95,78,55,58,30,41,58,73,42,64,74,87,58,73,82,1,40,91,14,23,75,68,37,65,0,74,10,96,97,49,14,69,36,50],
        [16,81,30,83,84,81,47,46,34,21,38,24,77,69,86,58,94,49,19,59,69,74,14,62,96,69,26,26,51,54,38,80,53,75,46,25,96,88,44,5,34,65,9,33,50,63,86,68,5,0,33,36,51,79,69,93,88,91,54,62,31,16,36,61,45,40,6,59,20,40,57,28,30,21,39,18,87,35,96,12,86,3,47,55,80,63,16,96,91,73,95,61,49,49,65,21,76,69,25,6,65,51,76,26,50,86,2,86,28,55,65,84,58,92,40,30,59,20,3,82,3,65,19,32,12,87,85,7,6,40,58,8,1,44,44,6,51,23,55,20,87,19,97,80,58,91,77,98,25,29,4,97,7,75,48,63,96,8,81,73,30,55,59,65,1,31,23,8,77,21,54,2,4,67,4,47,22,48,28,72,35,68,61,56,77,33,37,14,77,86,83,53,68,73,35,26,47,46,13,19,57,20,78,87,91,75,99,24,17,7,96,63,27,71,91,18,10,5,70,92,31,19,12,92,70,16,78,14,60,78,82,46,30,54,57,82,67,29,49,1,95,56,84,46,9,64,54,27,97,33,42,56,43,52,47,8,37,62,23,91,53,77,81,98,76,41,72,20,29,47,46,69,56,85,49,34,64,34,5,48,97,52,42,69,19,9,74,67,89,2,92,24,44,96,54,79,27,49,31,97,68,43,92,55,60,76,54,93,61,21,80,52,69,81,80,60,26,13,59,23,38,66,78,63,5,6,38,92,3,8,98,30,45,31,56,80,0,57,28,24,6,5,80,81,45,90,2,24,71,44,8,49,42,32,96,41,20,52,82,16,58,90,58,65,38,28,26,9,75,35,55,17,74,59,75,99,65,96,45,41,39,27,72,87,92,51,62,37,13,14,32,16,41,8,8,94,19,93,74,92,86,44,33,3,27,32,21,28,18,81,5,6,30,92,79,56,88,5,43,44,60,42,48,50,4,97,8,16,75,27,72,49,1,25,3,83,58,69,85,55,32,60,74,23,56,14,40,51,59,40,56,50,55,32,82,92,85,96,37,58,79,39,26,19,68,23,51,99,77,23,65,43,12,59,4,95,73,91,50,60,66,4,73,0,16,58,35,92,29,89,61,77,80,35,15,71,83,11,69,77,97,22,0,73,42,51,25,32,92,14,26,81,89,89,75,3,69,71,12,43,89,78,71,19,24,49,0,95,48,66,67,38,26,60,20,80,32,7,42,83,75,22,60,25,75,44,55,55,76,60,14,31,2,76,0,58,53,15,57,13,89,96,36,26,17,65,20,42,32,62,62,1,74,29,24,63,74,75,23,34,60,13,94,7,85,75,13,91,97,90,95,51,60,23,11,25,92,18,29,12,50,16,43,45,61,17,42,51,3,8,97,7,5,79,30,41,61,70,32,30,84,42,78,19,63,88,26,99,3,97,48,1,24,13,11,19,5,26,76,56,72,82,63,29,86,44,62,24,21,61,10,25,46,66,88,72,14,68,64,98,30,0,79,45,86,45,99,9,84,81,17,41,50,80,70,85,73,52,9,23,92,56,89,58,34,4,57,82,69,73,82,28,55,55,16,82,55,90,97,32,58,91,53,55,1,62,50,99,12,33,31,42,46,40,88,33,56,74,79,18,81,7,58,33,11,35,33,69,5,96,32,73,79,68,42,35,40,41,8,10,85,83,61,88,63,27,86,14,8,7,4,94,88,74,36,98,16,75,39,33,57,90,44,53,74,34,21,11,74,95,54,7,89,54,98,66,92,82,32,61,4,33,5,9,59,68,34,90,35,47,40,53,42,63,44,95,65,96,60,41,35,76,57,38,90,44,27,77,87,19,28,94,76,99,46,90,86,7,36,40,66,62,96,30,3,19,4,9,62,20,41,43,28,8,10,21,16,42,49,61,30,10,68,35,92,6,60,78,51,5,89,42,97,96,98,85,69,60,20,27,92,50,15,72,97,36,6,57,25,22,74,65,33,93,27,81,11,92,74,57,75,38,5,2,29,5,68,10,99,21,40,79,48,34,5,61,12,3,26,59,38,25,33,74,88,37,87,92,14,43,48,4,14,60,62,98,27,25,72,91,64,51,55,78,16,22,19,94,12,22,91,39,38,18,61,79,28,38,20,91,74,71,79,8,28,20,38,66,87,31,66,32,55,93,0,3,27,59,31,44,61,72,90,86,55,31,49,68,94,73,94,99,78,77,35,42,16,56,57,17,78,19,52,14,90,33,47,44,1,65,40,83,20,6,4,46,23,22,30,97]
    ), 'result': 500},
]
from leettest import test
test(Solution().findLength, testcases)