Sponsored
Sponsored
This approach uses a 2D DP array where dp[i][j] represents the length of the longest common subarray ending at nums1[i-1] and nums2[j-1]. Initialize the DP table with zeros. If nums1[i-1] == nums2[j-1], set dp[i][j] = dp[i-1][j-1] + 1, otherwise set it to 0. Track the maximum length found throughout the process.
Time Complexity: O(n * m), where n and m are the lengths of nums1 and nums2, respectively. Space Complexity: O(n * m) due to the DP table.
1class Solution:
2 def findLength(self, nums1: List[int], nums2: List[int]) -> int:
3 max_len = 0
4 dp = [[0] * (len(nums2) + 1) for _ in range(len(nums1) + 1)]
5 for i in range(1, len(nums1) + 1):
6 for j in range(1, len(nums2) + 1):
7 if nums1[i - 1] == nums2[j - 1]:
8 dp[i][j] = dp[i - 1][j - 1] + 1
9 max_len = max(max_len, dp[i][j])
10 return max_lenPython solution uses a list of lists to implement the DP table. For each pair of indices, it checks for matching elements and updates the max length accordingly.
This approach involves using a sliding window over the two arrays with the help of a hashing method to check potential matches of subarrays. By varying the window size, you can find the length of the longest matching subarray without needing a full DP table.
Time Complexity: O(n * m), Space Complexity: O(1).
1
The C solution selectively shifts and iterates over subarrays, checking integer matches directly as the two pointers overlap, recalculating lengths and ensuring a memory-efficient solution.