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].

Variant - Longest common browsing history

We have some historical clickstream data gathered from our site anonymously using cookies. The histories contain URLs that users have visited in chronological order.

Write a function that takes two users’ browsing histories as input and returns the longest contiguous sequence of URLs that appear in both.

For example, given the following two users’ histories:

1
2

user1 = ['/home', '/register', '/login', '/user', '/one', '/two']
user2 = ['/home', '/red', '/login', '/user', '/one', '/pink']

You should return the following:

1

['/login', '/user', '/one']

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.

Variant - Longest Common Browsing History

Method 1 – Dynamic Programming for Strings

Intuition

This is the same as the repeated subarray problem, but with strings instead of integers. Use dynamic programming to find the longest common contiguous sequence of URLs.

Approach

  1. Create a DP table dp where dp[i][j] is the length of the longest common contiguous sequence ending at user1[i-1] and user2[j-1].
  2. If user1[i-1] == user2[j-1], set dp[i][j] = dp[i-1][j-1] + 1; otherwise, set dp[i][j] = 0.
  3. Track the maximum length max_len and the ending index end_idx in user1.
  4. Return the subarray user1[end_idx-max_len:end_idx] as the answer.

Code

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

class Solution:
    def longest_common_history(self, user1: list[str], user2: list[str]) -> list[str]:
        m, n = len(user1), len(user2)
        dp = [[0]*(n+1) for _ in range(m+1)]
        max_len = 0
        end_idx = 0
        for i in range(1, m+1):
            for j in range(1, n+1):
                if user1[i-1] == user2[j-1]:
                    dp[i][j] = dp[i-1][j-1] + 1
                    if dp[i][j] > max_len:
                        max_len = dp[i][j]
                        end_idx = i
        return user1[end_idx - max_len:end_idx]

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 contiguous sequence for each pair of indices.