Leetcode

Maximum Length of Repeated Subarray

Approach 1: 2D DP

  • Time:O(mn)
  • Space:O(mn)

C++

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] := max length of nums1[i:] and nums2[j:]
    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;
  }
};

JAVA

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] := max length of nums1[i:] and nums2[j:]
    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;
  }
}

Python

class Solution:
  def findLength(self, nums1: List[int], nums2: List[int]) -> int:
    m = len(nums1)
    n = len(nums2)
    ans = 0
    # dp[i][j] := max length of nums1[i:] and nums2[j:]
    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)

C++

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;
  }
};

JAVA

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;
  }
}

Python

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):
        dp[j] = dp[j + 1] + 1 if a == b else 0
        ans = max(ans, dp[j])

    return ans