Problem Description

You are given two integer arrays nums1 and nums2. Your task is to find the maximum length of a subarray that appears in both arrays.

A subarray is a contiguous sequence of elements within an array. For example, if nums1 = [1,2,3,4], then [2,3] is a subarray of nums1.

The problem asks you to find the longest common subarray that exists in both nums1 and nums2. The subarray must be exactly the same in both arrays (same elements in the same order) and must be contiguous.

For example:

• If nums1 = [1,2,3,2,1] and nums2 = [3,2,1,4,7], the longest common subarray is [3,2,1] with length 3
• If nums1 = [0,0,0,0,0] and nums2 = [0,0,0,0,0], the longest common subarray is [0,0,0,0,0] with length 5

The solution uses dynamic programming where f[i][j] represents the length of the longest common subarray ending at position i-1 in nums1 and position j-1 in nums2. When nums1[i-1] == nums2[j-1], we extend the previous common subarray by 1, otherwise the length is 0. The answer is the maximum value found in the entire DP table.

Intuition

The key insight is recognizing that this is a classic dynamic programming problem similar to finding the longest common substring between two strings.

When we look for common subarrays, we need to track contiguous sequences. If we find matching elements at positions i and j in the two arrays, we want to know: can we extend a previous common subarray that ended just before these positions?

This leads us to think about building up solutions from smaller subproblems. If nums1[i] == nums2[j], and we already know the length of the longest common subarray ending at nums1[i-1] and nums2[j-1], then we can extend that length by 1.

The dynamic programming approach emerges naturally from this observation:

• If elements match at positions i and j, the length of common subarray ending here is 1 + length of common subarray ending at (i-1, j-1)
• If elements don't match, we can't have a common subarray ending at these positions, so the length is 0

We create a 2D table f[i][j] where each cell represents the length of the longest common subarray ending exactly at position i-1 in nums1 and j-1 in nums2. By computing all possible ending positions and keeping track of the maximum length found, we get our answer.

The reason we use indices i-1 and j-1 instead of i and j directly is to handle the base case cleanly - when there's no previous element, the DP table has 0s at the boundaries, which correctly represents that there's no common subarray to extend from.

Learn more about Binary Search, Dynamic Programming and Sliding Window patterns.

Solution Approach

The solution implements a bottom-up dynamic programming approach using a 2D table to find the maximum length of common subarrays.

Data Structure:

• A 2D DP table f of size (m+1) × (n+1) where m = len(nums1) and n = len(nums2)
• Each cell f[i][j] stores the length of the longest common subarray ending at nums1[i-1] and nums2[j-1]

Algorithm Steps:

1. Initialize the DP table: Create a 2D array f with dimensions (m+1) × (n+1) filled with zeros. The extra row and column handle the base cases where we have empty subarrays.

2. Fill the DP table: Iterate through each position in both arrays:

   for i in range(1, m + 1):
       for j in range(1, n + 1):

3. Check for matching elements: At each position (i, j), compare nums1[i-1] with nums2[j-1]:

   • If they match: f[i][j] = f[i-1][j-1] + 1
     • This extends the common subarray that ended at the previous positions
   • If they don't match: f[i][j] remains 0 (already initialized)
     • No common subarray can end at these mismatched positions

4. Track the maximum: After each update where elements match, update the answer:

   ans = max(ans, f[i][j])

5. Return the result: The variable ans holds the maximum length found across all possible ending positions.

Time Complexity: O(m × n) where m and n are the lengths of the two arrays, as we fill each cell of the DP table once.

Space Complexity: O(m × n) for the 2D DP table.

The beauty of this approach is that it systematically considers all possible ending positions for common subarrays and builds up the solution incrementally, ensuring we find the global maximum.

Example Walkthrough

Let's walk through a small example with nums1 = [1,2,3,2,1] and nums2 = [3,2,1,4].

Step 1: Initialize the DP table We create a table f of size (6 × 5) filled with zeros. The indices represent:

• Rows 0-5 for nums1 (with row 0 as padding)
• Columns 0-4 for nums2 (with column 0 as padding)

Initial table:

    0  1  2  3  4
    -  3  2  1  4
0 - 0  0  0  0  0
1 1 0  0  0  0  0
2 2 0  0  0  0  0
3 3 0  0  0  0  0
4 2 0  0  0  0  0
5 1 0  0  0  0  0

Step 2: Fill the table row by row

For i=1, j=1: Compare nums1[0]=1 with nums2[0]=3 → No match, f[1][1]=0

For i=1, j=2: Compare nums1[0]=1 with nums2[1]=2 → No match, f[1][2]=0

For i=1, j=3: Compare nums1[0]=1 with nums2[2]=1 → Match! f[1][3]=f[0][2]+1=1, ans=1

Continuing this process for all cells:

When i=3, j=1: nums1[2]=3 matches nums2[0]=3 → f[3][1]=f[2][0]+1=1

When i=4, j=2: nums1[3]=2 matches nums2[1]=2 → f[4][2]=f[3][1]+1=2, ans=2

When i=5, j=3: nums1[4]=1 matches nums2[2]=1 → f[5][3]=f[4][2]+1=3, ans=3

Final DP table:

    0  1  2  3  4
    -  3  2  1  4
0 - 0  0  0  0  0
1 1 0  0  0  1  0
2 2 0  0  1  0  0
3 3 0  1  0  0  0
4 2 0  0  2  0  0
5 1 0  0  0  3  0

Step 3: Result The maximum value in the table is 3, which corresponds to the common subarray [3,2,1]:

• In nums1: positions 2,3,4 → [3,2,1]
• In nums2: positions 0,1,2 → [3,2,1]

The key insight: f[5][3]=3 tells us there's a common subarray of length 3 ending at nums1[4] and nums2[2]. By tracing back diagonally (from f[5][3] to f[4][2] to f[3][1]), we can see how the common subarray was built up incrementally.

Solution Implementation

Time and Space Complexity

Time Complexity: O(m * n) where m is the length of nums1 and n is the length of nums2. The algorithm uses two nested loops that iterate through all possible positions in the DP table. The outer loop runs m times (from 1 to m+1), and the inner loop runs n times (from 1 to n+1). Each cell computation takes O(1) time, resulting in a total time complexity of O(m * n).

Space Complexity: O(m * n) where m is the length of nums1 and n is the length of nums2. The algorithm creates a 2D DP table f with dimensions (m+1) × (n+1) to store the lengths of common subarrays ending at each position. This requires O((m+1) * (n+1)) = O(m * n) space. The additional variables ans, i, and j use O(1) space, so the overall space complexity is O(m * n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Index Confusion with DP Table Dimensions

One of the most common mistakes is confusing the indexing between the DP table and the original arrays. The DP table has dimensions (len1+1) × (len2+1), but the arrays are indexed from 0 to len-1.

Pitfall Example:

# WRONG: Forgetting to subtract 1 when accessing array elements
if nums1[i] == nums2[j]:  # This will cause IndexError
    dp[i][j] = dp[i-1][j-1] + 1

Correct Approach:

# CORRECT: Remember dp[i][j] corresponds to nums1[i-1] and nums2[j-1]
if nums1[i-1] == nums2[j-1]:
    dp[i][j] = dp[i-1][j-1] + 1

2. Space Optimization Oversight

While the 2D DP solution works correctly, it uses O(m×n) space which can be excessive for large arrays. Since we only need the previous row to compute the current row, we can optimize space.

Space-Optimized Solution:

def findLength(self, nums1: List[int], nums2: List[int]) -> int:
    len1, len2 = len(nums1), len(nums2)
    # Use only two rows instead of full 2D table
    prev = [0] * (len2 + 1)
    curr = [0] * (len2 + 1)
    max_length = 0
  
    for i in range(1, len1 + 1):
        for j in range(1, len2 + 1):
            if nums1[i-1] == nums2[j-1]:
                curr[j] = prev[j-1] + 1
                max_length = max(max_length, curr[j])
            else:
                curr[j] = 0
        prev, curr = curr, prev
  
    return max_length

3. Forgetting to Reset Values When Elements Don't Match

When using space optimization or reusing arrays, failing to reset values when elements don't match can lead to incorrect results.

Pitfall Example:

# WRONG: Not resetting curr[j] when elements don't match
for j in range(1, len2 + 1):
    if nums1[i-1] == nums2[j-1]:
        curr[j] = prev[j-1] + 1
    # Missing: else curr[j] = 0

This leaves old values in curr[j] which can corrupt future calculations.

4. Misunderstanding the Problem - Subarray vs Subsequence

A critical mistake is confusing this problem with the Longest Common Subsequence (LCS) problem. Remember:

• Subarray: Must be contiguous
• Subsequence: Can skip elements

Wrong Approach (LCS logic):

# This finds longest common subsequence, NOT subarray
if nums1[i-1] == nums2[j-1]:
    dp[i][j] = dp[i-1][j-1] + 1
else:
    dp[i][j] = max(dp[i-1][j], dp[i][j-1])  # WRONG for subarray problem

For the subarray problem, when elements don't match, the length must be 0, not the maximum of adjacent cells.