Maximum Length of Repeated Subarray - Practice Coding Problems

Maximum Length of Repeated Subarray - Problem

Array Binary Search Dynamic Programming Sliding Window Rolling Hash Hash Function Medium

Given two integer arrays nums1 and nums2, return the maximum length of a subarray that appears in both arrays.

A subarray is a contiguous sequence of elements within an array. For example, in the array [1,2,3,4], the subarrays include [1], [2,3], [3,4], [1,2,3], etc.

The goal is to find the longest common subarray between the two given arrays.

Input & Output

Example 1 — Basic Common Subarray

$ Input: nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]

› Output: 3

💡 Note: The longest common subarray is [3,2,1] which appears in nums1 at indices 2-4 and in nums2 at indices 0-2. Length = 3.

Example 2 — Partial Match

$ Input: nums1 = [0,0,0,0,1], nums2 = [1,0,0,0,0]

› Output: 4

💡 Note: The longest common subarray is [0,0,0,0] which appears in nums1 at indices 0-3 and in nums2 at indices 1-4. Length = 4.

Example 3 — No Common Subarray

$ Input: nums1 = [1,2,3], nums2 = [4,5,6]

› Output: 0

💡 Note: There are no common elements between the arrays, so the maximum length is 0.

Constraints

1 ≤ nums1.length, nums2.length ≤ 1000
0 ≤ nums1[i], nums2[i] ≤ 100

Visualization

Tap to expand

Understanding the Visualization

Input Arrays

Two integer arrays nums1 and nums2

Find Common Subarrays

Identify all contiguous sequences that appear in both arrays

Return Maximum Length

Output the length of the longest common subarray

Key Takeaway

🎯 Key Insight: Use dynamic programming to efficiently track common subarray lengths at each position pair

Asked in

G Google 45 f Facebook 38 a Amazon 32 M Microsoft 28

The key insight is to use dynamic programming to track the length of common subarrays ending at each position. Best approach uses a 2D DP table where dp[i][j] represents the length of the common subarray ending at nums1[i-1] and nums2[j-1]. Time: O(n×m), Space: O(n×m) or O(m) with optimization.

Common Approaches

Approach	Time	Space	Notes
✓ Dynamic Programming	O(n×m)	O(n×m)	Build a 2D table to track matching subarray lengths ending at each position
Brute Force	O(n²×m)	O(1)	Check all possible subarrays from both arrays and find the longest match
Space-Optimized DP	O(n×m)	O(m)	Use only two 1D arrays instead of a full 2D table to save space

Dynamic Programming — Algorithm Steps

Create 2D DP table of size (n+1) x (m+1)
If nums1[i-1] == nums2[j-1], set dp[i][j] = dp[i-1][j-1] + 1
Track the maximum value in the DP table

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize DP Table

Create (n+1) x (m+1) table with zeros

Fill Diagonal

When elements match, dp[i][j] = dp[i-1][j-1] + 1

Track Maximum

Keep the largest value seen in the table

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* nums1, int nums1Size, int* nums2, int nums2Size) {
    // Create 2D DP array
    int** dp = (int**)malloc((nums1Size + 1) * sizeof(int*));
    for (int i = 0; i <= nums1Size; i++) {
        dp[i] = (int*)calloc(nums2Size + 1, sizeof(int));
    }
    
    int maxLength = 0;
    
    for (int i = 1; i <= nums1Size; i++) {
        for (int j = 1; j <= nums2Size; j++) {
            if (nums1[i - 1] == nums2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
                if (dp[i][j] > maxLength) {
                    maxLength = dp[i][j];
                }
            }
        }
    }
    
    // Free memory
    for (int i = 0; i <= nums1Size; i++) {
        free(dp[i]);
    }
    free(dp);
    
    return maxLength;
}

int main() {
    char line1[1000], line2[1000];
    fgets(line1, sizeof(line1), stdin);
    fgets(line2, sizeof(line2), stdin);
    
    // Simple array parsing
    int nums1[100], nums2[100];
    int nums1Size = 0, nums2Size = 0;
    
    // Parse first array
    char* token = strtok(line1, "[],\n");
    while (token != NULL) {
        nums1[nums1Size++] = atoi(token);
        token = strtok(NULL, "[],\n");
    }
    
    // Parse second array
    token = strtok(line2, "[],\n");
    while (token != NULL) {
        nums2[nums2Size++] = atoi(token);
        token = strtok(NULL, "[],\n");
    }
    
    printf("%d\n", solution(nums1, nums1Size, nums2, nums2Size));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n×m)

Single nested loop through both arrays to fill DP table

✓ Linear Growth

Space Complexity

O(n×m)

2D DP table storing lengths for each position pair

⚡ Linearithmic Space

125.0K Views

Medium Frequency

~25 min Avg. Time

2.5K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Dynamic Programming — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler