<p>Given two integer arrays <code>nums1</code> and <code>nums2</code>, return <em>the maximum length of a subarray that appears in <strong>both</strong> arrays</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
<strong>Output:</strong> 3
<strong>Explanation:</strong> The repeated subarray with maximum length is [3,2,1].
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0]
<strong>Output:</strong> 5
<strong>Explanation:</strong> The repeated subarray with maximum length is [0,0,0,0,0].
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums1.length, nums2.length &lt;= 1000</code></li>
	<li><code>0 &lt;= nums1[i], nums2[i] &lt;= 100</code></li>
</ul>

class Solution:
    def findLength(self, nums1: List[int], nums2: List[int]) -> int:
        # DP 
        # if nums1[i] == num2[j] -> we can check if nums1[i-1] == nums2[j-1]
        # that would form a longer subarray
        # use this property, use DP to fill out the grid of nxm
        # value of DP means the length of the subarray we can form
        # from nums1[i] == nums2[j]
        # we fill dp from right bottom, when nums1[i] == num2[j],
        # the length of subarra we can form from dp[i][j] is 
        # dp[i+1][j+1] + 1
        # O(nm), O(nm)
        n = len(nums1)
        m = len(nums2)
        # add additional row/column so i+1, j+1 would never get out of range
        dp = [[0 for _ in range(m + 1)] for _ in range(n + 1)]

        for i in range(n-1, -1, -1):
            for j in range(m-1, -1, -1):
                if nums1[i] == nums2[j]:
                    dp[i][j] = dp[i+1][j+1] + 1

        return max([max(row) for row in dp])
        

        # 1. find all subarray of nums1 and nums2 to find one
        # 2. Select a starting num from nums1, find that element in nums2
        # and see how long we can form the subarray. do this repeatly to find
        # repeated subarray 
        # O(nm(n+m)), O(min(n, m))
        # 3. Guess the subarray length - starting with min(len(nums1), len(nums2)) // 2
        # and try to find a repeated subarry of that length by find all possible
        # subarry of that lenght from nums1 and add them into a set
        # then find all possible subarray of that length from nums2 and see if
        # we can also find it in the set
        # if found, try the length between current and upper bound, if not found,
        # try the length between current and lower bound until finding the max length of 
        # repeated subarray
        # O((n+m)* log min(n, m)), O(min(n,m)), where n is the len of nums1 and m is
        # the length of nums2
        # Guess the subarray length
        """
        if len(nums1) > len(nums2):
            nums1, nums2 = nums2, nums1

        n = len(nums1)
        m = len(nums2)
        low = 0
        high = n
        ans = 0

        def found_array(arr_len):
            pool = set()
            for i in range(n - arr_len + 1):
                pool.add(tuple(nums1[i:i+arr_len]))

            for i in range(m - arr_len + 1):
                subarray = nums2[i:i+arr_len]
                if tuple(subarray) in pool:
                    return True

            return False


        while low < high:
            # need +1 to include the case that the answer is n
            mid = (low + high + 1) // 2
            if not found_array(mid):
                high = mid - 1
            else:
                ans = mid
                low = mid

        return ans

        """
42700