mediumArraysPattern: Two Pointers
Longest Common Subarray Solution
Problem Statement
Given two integer arrays, `nums1` and `nums2`, return the length of the longest common subarray between them. A subarray is a contiguous non-empty sequence of elements within an array.
Examples
Example 1:
Input:nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
Output:3
Explanation: The longest common subarray is [3,2,1]. Its length is 3.
Example 2:
Input:nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0]
Output:5
Explanation: The longest common subarray is [0,0,0,0,0]. Its length is 5.
Example 3:
Input:nums1 = [1,2,3,4,5], nums2 = [6,7,8,9,10]
Output:0
Explanation: There is no common subarray between the two arrays. Its length is 0.
Constraints
- 1 <= nums1.length, nums2.length <= 1000
- -1000 <= nums1[i], nums2[i] <= 1000
Time: O(m*n) Space: O(m*n)
Use dynamic programming. Create a 2D DP table where `dp[i][j]` stores the length of the longest common subarray ending at `nums1[i-1]` and `nums2[j-1]`. If `nums1[i-1] == nums2[j-1]`, then `dp[i][j] = dp[i-1][j-1] + 1`. The answer is the maximum value in the DP table.
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
def find_length(nums1: list[int], nums2: list[int]) -> int:
m = len(nums1)
n = len(nums2)
if m == 0 or n == 0:
return 0
dp = [[0] * (n + 1) for _ in range(m + 1)]
max_length = 0
for i in range(1, m + 1):
for j in range(1, n + 1):
if nums1[i - 1] == nums2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
max_length = max(max_length, dp[i][j])
else:
dp[i][j] = 0
return max_length