Skip to content

718. Maximum Length of Repeated Subarray 👍

Approach 1: 2D DP

  • Time: $O(mn)$
  • Space: $O(mn)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
 public:
  int findLength(vector<int>& nums1, vector<int>& nums2) {
    const int m = nums1.size();
    const int n = nums2.size();
    int ans = 0;
    // dp[i][j] := the maximum length of a subarray that appears in both
    // nums1[i..m) and nums2[j..n)
    vector<vector<int>> dp(m + 1, vector<int>(n + 1));

    for (int i = m - 1; i >= 0; --i)
      for (int j = n - 1; j >= 0; --j)
        if (nums1[i] == nums2[j]) {
          dp[i][j] = dp[i + 1][j + 1] + 1;
          ans = max(ans, dp[i][j]);
        }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
  public int findLength(int[] nums1, int[] nums2) {
    final int m = nums1.length;
    final int n = nums2.length;
    int ans = 0;
    // dp[i][j] := the maximum length of a subarray that appears in both
    // nums1[i..m) and nums2[j..n)
    int[][] dp = new int[m + 1][n + 1];

    for (int i = m - 1; i >= 0; --i)
      for (int j = n - 1; j >= 0; --j)
        if (nums1[i] == nums2[j]) {
          dp[i][j] = dp[i + 1][j + 1] + 1;
          ans = Math.max(ans, dp[i][j]);
        }

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
  def findLength(self, nums1: List[int], nums2: List[int]) -> int:
    m = len(nums1)
    n = len(nums2)
    ans = 0
    # dp[i][j] := the maximum length of a subarray that appears in both
    # nums1[i..m) and nums2[j..n)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in reversed(range(m)):
      for j in reversed(range(n)):
        if nums1[i] == nums2[j]:
          dp[i][j] = dp[i + 1][j + 1] + 1
          ans = max(ans, dp[i][j])

    return ans

Approach 2: 1D DP

  • Time: $O(mn)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
 public:
  int findLength(vector<int>& nums1, vector<int>& nums2) {
    const int m = nums1.size();
    const int n = nums2.size();
    int ans = 0;
    vector<int> dp(n + 1);

    for (int i = m - 1; i >= 0; --i)
      for (int j = 0; j < n; ++j) {  // The order is important.
        dp[j] = nums1[i] == nums2[j] ? dp[j + 1] + 1 : 0;
        ans = max(ans, dp[j]);
      }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
  public int findLength(int[] nums1, int[] nums2) {
    final int m = nums1.length;
    final int n = nums2.length;
    int ans = 0;
    int[] dp = new int[n + 1];

    for (int i = m - 1; i >= 0; --i)
      for (int j = 0; j < n; ++j) { // The order is important.
        dp[j] = nums1[i] == nums2[j] ? dp[j + 1] + 1 : 0;
        ans = Math.max(ans, dp[j]);
      }

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
  def findLength(self, nums1: List[int], nums2: List[int]) -> int:
    ans = 0
    dp = [0] * (len(nums2) + 1)

    for a in reversed(nums1):
      for j, b in enumerate(nums2):  # The order is important.
        dp[j] = dp[j + 1] + 1 if a == b else 0
        ans = max(ans, dp[j])

    return ans