Skip to content

Files

Latest commit

28a4504 · Aug 10, 2023

History

History
105 lines (87 loc) · 2.87 KB

718.maximum-length-of-repeated-subarray.md

File metadata and controls

105 lines (87 loc) · 2.87 KB

Brute Force (TLE)

fun findLength(nums1: IntArray, nums2: IntArray): Int {
    var max = 0
    for (i in 0 until nums1.size) {
        for (j in 0 until nums2.size) {
            var k = 0
            // Find the common subarray, it takes O(m * n * min(m, n)) = O(n^3)
            while (i + k < nums1.size && j + k < nums2.size && nums1[i + k] == nums2[j + k]) {
                k++
                max = if (k > max) k else max
            }
        }
    }
    return max
}

Dynamic Programming

It's LCS variant, here we're looking for the longest common subarray (not subsequence), it has the optimal substructure: dp[i][j] = 1 + dp[i - 1][j - 1] when A[i] == B[j].

But the difference between subsequence and subarray is that it must be continuous for subarray, so dp[i][j] = 0 when A[i] != B[j].

fun findLength(nums1: IntArray, nums2: IntArray): Int {
    val m = nums1.size
    val n = nums2.size
    val dp = Array(m + 1) { _ -> IntArray(n + 1) }
    var max = 0
    
    for (i in 0 until m) {
        dp[i][0] = 0
    }
    for (j in 0 until n) {
        dp[0][j] = 0
    }
    
    for (i in 1..m) {
        for (j in 1..n) {
            dp[i][j] = if (nums1[i - 1] == nums2[j - 1]) {
                1 + dp[i - 1][j - 1]
            } else {
                0
            }
            
            max = if (dp[i][j] > max) dp[i][j] else max
        }
    }
    return max
}
  • Time Complexity: O(m * n) where m and n are the length of two strings, respectively.
  • Space Complexity: O(m * n) for 2D dp array.

Dynamic Programming (Space Optimization)

Since every dp[i][j] depends only on dp[i - 1][j - 1], we can store as dp[2][j] for space optimization.

     j, j+1
i    X
       \
i+1      Y

n1 = "23"
n2 = "123"
      
   0, 1, 2, 3  // index
0  0  X
1        Y     // Y depends on X
2           Z  // Z depends on Y

// So we store for X, Y row, then shift to Y, Z row.
fun findLength(nums1: IntArray, nums2: IntArray): Int {
    // TODO: Here we should use the shorter array as the first array to reduce the space complexity.
    val dp = Array(2) { IntArray(nums2.size + 1) { 0 }
    val max = 0
    for (i in 1..nums1.size) {
        for (j in 1..nums2.size) {
            if (nums1[i - 1] == nums2[j - 1]) {
                dp[0][j] = 1 + dp[1][j - 1]
            }
            max = maxOf(max, dp[0][j])
        }

        // shift dp[1] to dp[0]
        for (j in 0..nums2.size) {
            dp[1][j] = dp[0][j]
            // This is nessary to clean up the value of dp[0][j] for next iteration.
            dp[0][j] = 0
        }
    }
    return max
}
  • Time Complexity: O(m * n) where m and n are the length of two strings, respectively.
  • Space Complexity: O(min(n, n).