Problem

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

Examples

Example 1:

1
2
3
4
5

Input:
nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
Output:
 3
Explanation: The repeated subarray with maximum length is [3,2,1].

Example 2:

1
2
3
4
5

Input:
nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0]
Output:
 5
Explanation: The repeated subarray with maximum length is [0,0,0,0,0].

Solution

Method 1 – Dynamic Programming

Intuition

Use dynamic programming to find the length of the longest common subarray ending at each pair of indices in nums1 and nums2.

Approach

  1. Create a DP table where dp[i][j] is the length of the longest common subarray ending at nums1[i-1] and nums2[j-1].
  2. If nums1[i-1] == nums2[j-1], set dp[i][j] = dp[i-1][j-1] + 1; otherwise, dp[i][j] = 0.
  3. Track the maximum value in the DP table.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
public:
    int findLength(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size(), n = nums2.size(), res = 0;
        vector<vector<int>> dp(m+1, vector<int>(n+1));
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (nums1[i-1] == nums2[j-1]) {
                    dp[i][j] = dp[i-1][j-1] + 1;
                    res = max(res, dp[i][j]);
                }
            }
        }
        return res;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

func findLength(nums1 []int, nums2 []int) int {
    m, n := len(nums1), len(nums2)
    dp := make([][]int, m+1)
    for i := range dp { dp[i] = make([]int, n+1) }
    res := 0
    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            if nums1[i-1] == nums2[j-1] {
                dp[i][j] = dp[i-1][j-1] + 1
                if dp[i][j] > res { res = dp[i][j] }
            }
        }
    }
    return res
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    public int findLength(int[] nums1, int[] nums2) {
        int m = nums1.length, n = nums2.length, res = 0;
        int[][] dp = new int[m+1][n+1];
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (nums1[i-1] == nums2[j-1]) {
                    dp[i][j] = dp[i-1][j-1] + 1;
                    res = Math.max(res, dp[i][j]);
                }
            }
        }
        return res;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    fun findLength(nums1: IntArray, nums2: IntArray): Int {
        val m = nums1.size
        val n = nums2.size
        val dp = Array(m+1) { IntArray(n+1) }
        var res = 0
        for (i in 1..m) {
            for (j in 1..n) {
                if (nums1[i-1] == nums2[j-1]) {
                    dp[i][j] = dp[i-1][j-1] + 1
                    res = maxOf(res, dp[i][j])
                }
            }
        }
        return res
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution:
    def findLength(self, nums1: list[int], nums2: list[int]) -> int:
        m, n = len(nums1), len(nums2)
        dp = [[0]*(n+1) for _ in range(m+1)]
        res = 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
                    res = max(res, dp[i][j])
        return res
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

impl Solution {
    pub fn find_length(nums1: Vec<i32>, nums2: Vec<i32>) -> i32 {
        let m = nums1.len();
        let n = nums2.len();
        let mut dp = vec![vec![0; n+1]; m+1];
        let mut res = 0;
        for i in 1..=m {
            for j in 1..=n {
                if nums1[i-1] == nums2[j-1] {
                    dp[i][j] = dp[i-1][j-1] + 1;
                    res = res.max(dp[i][j]);
                }
            }
        }
        res
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    findLength(nums1: number[], nums2: number[]): number {
        const m = nums1.length, n = nums2.length;
        const dp: number[][] = Array.from({length: m+1}, () => Array(n+1).fill(0));
        let res = 0;
        for (let i = 1; i <= m; ++i) {
            for (let j = 1; j <= n; ++j) {
                if (nums1[i-1] === nums2[j-1]) {
                    dp[i][j] = dp[i-1][j-1] + 1;
                    res = Math.max(res, dp[i][j]);
                }
            }
        }
        return res;
    }
}

Complexity

  • ⏰ Time complexity: O(m*n)
    • We fill a DP table of size m x n, iterating over all pairs of indices.
  • 🧺 Space complexity: O(m*n)
    • The DP table stores the length of the longest common subarray for each pair of indices.