Problem Explanation

This problem asks to find out the maximum length of repeated subarrays from two given integer arrays. Basically, we have to find out the longest common contiguous subarray.

Let's take an example for better understanding.

Example :

1
2
3Input : 
4
5nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
6
7Output :
8 
93

In the above example, the longest common contiguous subarray is [3,2,1]. So, the output is 3.

Approach

This problem can be solved using Dynamic Programming. We will first initialize a 2D array dp of size m*n where m and n are the lengths of the input arrays respectively. dp[i][j] will represent the maximum length of repeated subarray starting at index i in nums1 and index j in nums2. Then, we iterate the given arrays in reverse order, and if nums1[i] == nums2[j], then dp[i][j] = dp[i+1][j+1]+1. Finally, we return the maximum value in the 2D array dp.

1
2
3nums1 : [1,2,3,2,1]
4nums2 : [3,2,1,4,7]

If we apply the above approach, the dp would look like the following after completion of the iterations.

1
2
3dp: [[0, 3, 2, 1, 0, 0], 
4     [0, 2, 1, 0, 0, 0], 
5     [3, 1, 0, 0, 0, 0], 
6     [2, 0, 0, 0, 0, 0], 
7     [1, 0, 0, 0, 0, 0], 
8     [0, 0, 0, 0, 0, 0]]

Here, the maximum value is 3, which is the length of the longest common subarray [3,2,1].

Solutions

Python

1
2python
3class Solution:
4    def findLength(self, nums1, nums2):
5        m, n = len(nums1), len(nums2)
6        dp = [[0]*(n+1) for _ in range(m+1)]
7        ans = 0
8        
9        for i in range(m-1, -1, -1):
10            for j in range(n-1, -1, -1):
11                if nums1[i] == nums2[j]:
12                    dp[i][j] = dp[i+1][j+1] + 1
13                    ans = max(ans, dp[i][j])
14                    
15        return ans

Java

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

JavaScript

1
2javascript
3var findLength = function(nums1, nums2) {
4    let m = nums1.length, n = nums2.length, ans = 0;
5    let dp = Array.from(Array(m + 1), () => new Array(n + 1).fill(0));
6    for (let i = m - 1; i >= 0; --i) {
7      for (let j = n - 1; j >= 0; --j) {
8        if (nums1[i] === nums2[j]) 
9            dp[i][j] = dp[i + 1][j + 1] + 1;
10            ans = Math.max(ans, dp[i][j]);
11    }
12    return ans;
13};

C++

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

C#

1
2csharp
3public class Solution {
4    public int FindLength(int[] nums1, int[] nums2) {
5        int m = nums1.Length, n = nums2.Length, ans = 0;
6        int[,] dp = new int[m + 1, n + 1];
7        
8        for(int i = m-1; i >= 0; --i)
9        {
10            for(int j = n-1; j >= 0; --j)
11            {
12                if(nums1[i] == nums2[j])
13                {
14                    dp[i,j] = dp[i + 1,j + 1] + 1;
15                    ans = Math.Max(ans, dp[i,j]);
16                }
17            }
18        }
19        return ans;
20    }
21}

These are the algorithms you can use to solve the maximum length of repeated subarrays problem. As you can see from the examples, the logic remains the same across all versions, but the syntax changes according to the programming language used.

It's important to understand the theoretical approach in order to grasp the concept of dynamic programming. Once that is clear, implementation becomes easier.

Remember, the key aspect here is to construct a solution table (dp array) intelligently and use the pre-computed values to solve subsequent subproblems.

This approach of breaking down the problem into smaller subproblems, solving them separately and using that information to solve the original problem is the essence of dynamic programming. By mastering this technique, you can solve a numerous amount of programming-related challenges in an efficient manner.

As with any other skill, practice is the key. Try to work with problems of varying difficulty levels to have a better grasp of the concept and also to understand how to improve the efficiency of the solution using this method. When it comes to coding, there's always room for improvement, and there's always a new and exciting problem waiting to be solved. So, keep experimenting, keep coding!