<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:
        # LCS 
        # REVIEW LCS (commonly asked by palantir)

        # # DP (FOR LCS)
        # # O(n * m) time
        # # O(n * m) space

        # # going from right to left 
        # dp = [[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]:
        #             dp[i][j] = dp[i + 1][j + 1] + 1 

        # res = 0
        # for i in range(len(nums1)):
        #     for j in range(len(nums2)):
        #         if res < dp[i][j]:
        #             res = dp[i][j]
        # return res
        
    
        # Binary Search + Rolling Hash
        # O( (n + m) log( min(n, m) )) time 
        # O(m) space 
        def rolling_hash(arr, length, d, q): # d: size of digits/charset, q: big prime number 
            # Return [(hash value, start ind),...]

            if len(arr) < length:
                return [(0, 0)]

            # Precompute h -> used for removing from hash_value later
            #  h = d^(m-1) % q 

            h = 1
            for _ in range(length-1):
                h = (h * d) % q

            # Compute 1st hash value (arr[:length]) 
            hash_val = 0                
            for i in range(length):
                hash_val = ((d * hash_val) + arr[i]) % q

            hash_vals = [(hash_val, 0)]
            # Calculate all subsequent hashs (remove + add)
            for i in range(length, len(arr)):
                # remove (arr[i - length])
                hash_val = (d * (hash_val - (h * arr[i - length]) )) % q
                # add (arr[i])
                hash_val = (hash_val + arr[i]) % q

                # new hash starts from index i - length + 1 
                hash_vals.append((hash_val, i - length + 1))

            return hash_vals
        

        def check(mid, D, MOD):
            # check for substrings length mid + 1 is found in both
            is_found = False

            hashes = collections.defaultdict(list)
            for h_val, ind in rolling_hash(nums1, mid+1, D, MOD):
                hashes[h_val].append(ind)
            
            for h_val, i2 in rolling_hash(nums2, mid+1, D, MOD):
                # must manually check in case of hash collision
                for i1 in hashes[h_val]:
                    is_match = True
                    for _ in range(mid + 1):
                        if nums1[i1] != nums2[i2]:
                            is_match = False
                            break
                        i1 += 1
                        i2 += 1 
                    if is_match:
                        is_found = True 
                        break
                if is_found:
                    break 
            
            return is_found

        D = 10 # ?
        MOD = 10**9 + 7

        # instead of linear search on lengths (0 ~ m)
        # go with binary search
        
        left, right = 0, min(len(nums1), len(nums2)) - 1 
        
        while left <= right:
            mid = left + (right - left) // 2 

            is_found = check(mid, D, MOD)

            if is_found:
                left = mid + 1 
            else:
                right = mid - 1
        
        return right + 1 

17300