718. Maximum Length of Repeated Subarray
Problem Description
The problem is to find the maximum length of a subarray that appears in both given integer arrays nums1
and nums2
. A subarray is a contiguous part of an array. The challenge is to identify the longest sequence of elements that nums1
and nums2
have in common, wherever that sequence may appear within the arrays.
Thus, the key point in this challenge is to compare elements at different positions across both arrays and keep track of the length of the current matching subarrays, equipping ourselves to identify the maximum length out of these subarrays.
Intuition
Our approach leverages a classic technique in computer science known as dynamic programming. Specifically, we use a 2D array (let's call it f
) where f[i][j]
represents the length of the longest common subarray ending with nums1[i-1]
and nums2[j-1]
.
Here's the intuition broken down into steps:
-
Construct a 2D list
f
with dimensions(m+1) x (n+1)
, wherem
andn
are the lengths ofnums1
andnums2
, respectively. Initialize all elements to 0. -
Loop through each element in
nums1
(indexi
) andnums2
(indexj
). -
If we find a match (
nums1[i - 1] == nums2[j - 1]
), this extends a common subarray. Therefore, we setf[i][j]
to bef[i - 1][j - 1] + 1
, effectively saying, "the longest common subarray ending here is one longer than the longest at the previous indices. -
Track the maximum length found during this process with a variable
ans
. -
After exploring all elements from both arrays,
ans
holds the length of the longest matching subarray found.
Learn more about Binary Search, Dynamic Programming and Sliding Window patterns.
Solution Approach
The solution implements a dynamic programming approach to solve the problem efficiently by avoiding the recomputation of overlapping subproblems. Let's walk through the logical steps and explain how the solution is implemented:
-
Initialization: Create a 2D list
f
of size(m+1) x (n+1)
filled with zeros, wherem
andn
are the lengths ofnums1
andnums2
, respectively. Here, each elementf[i][j]
is meant to hold the length of the longest common subarray that ends with elementsnums1[i-1]
andnums2[j-1]
. -
Nested Loops for Comparison: Utilize two nested loops to iterate over both arrays. The outer loop runs through
nums1
using indexi
, while the inner loop runs throughnums2
using indexj
. Both indices start from 1 since the 0-th row and column off
will be used as a base for the dynamic programming algorithm and should remain zeroes. -
Matching Elements: Inside the inner loop, check if the elements
nums1[i-1]
andnums2[j-1]
match. This is important because we are looking for a common subarray, so we are only interested in matching elements. -
Updating
f
: If a match is found, updatef[i][j]
tof[i-1][j-1] + 1
. This step carries over the length from the previous matching subarray and adds one for the current match. It is the core of the dynamic programming approach as it builds upon previously computed values. -
Tracking the Maximum Length: Keep updating a variable
ans
with the maximum value in the 2D listf
as we go, by comparingans
withf[i][j]
at each step.
Following this logic, the final value held in ans
after the loops complete execution will be the length of the longest common subarray between nums1
and nums2
. This is because ans
is updated each time we extend the length of a subarray, and it only keeps the maximum length encountered.
The dynamic programming pattern here exploits the "optimal substructure" property of the problem (the longest subarray ending at an index can be found from longest subarrays ending at previous indices) and avoids redundant calculations, providing an optimally efficient solution.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach with small example arrays nums1
and nums2
.
Suppose nums1 = [1, 2, 8, 3]
and nums2 = [5, 1, 8, 3, 9]
.
-
Initialization: We create a 2D list
f
with dimensions(4+1) x (5+1)
(asnums1
has length 4 andnums2
has length 5), sof
will be a 5x6 grid of zeros. This grid will store the lengths of the longest common subarrays found to our point. -
Nested Loops for Comparison: Begin with nested loops; with
i
iterating from1
to4
(fornums1
) andj
iterating from1
to5
(fornums2
). -
Matching Elements & Updating
f
:-
When
i=1
andj=2
, we find thatnums1[0] == nums2[1]
(which is1
). So, we updatef[1][2]
tof[0][1] + 1
. Sincef[0][1]
is0
,f[1][2]
becomes1
. -
As loops continue, no more matches are found until
i=3
andj=3
, wherenums1[2] == nums2[2]
(which is8
);f[3][3]
is updated tof[2][2] + 1
andf[3][3]
becomes1
. -
Finally, at
i=4
andj=4
,nums1[3] == nums2[3]
(which is3
). Since we had a match at the previous indices (nums1[2] == nums2[2]
was8
),f[i][j]
becomesf[3][3] + 1
.f[3][3]
was1
, so nowf[4][4]
is2
. This is the longest subarray we've encountered.
-
-
Tracking the Maximum Length:
ans
is updated each timef[i][j]
is bigger than the currentans
. It starts at0
and becomes1
after the first match, and then2
after the last match.
The loops conclude with ans
holding the value 2
, which is the maximum length of a subarray that appears in both nums1
and nums2
(the subarray being [8, 3]
).
This walk-through has demonstrated how the dynamic programming approach efficiently solves the problem by using previously computed values to build up a solution, avoiding unnecessary recomputation.
Solution Implementation
1from typing import List
2
3class Solution:
4 def findLength(self, nums1: List[int], nums2: List[int]) -> int:
5 # Get the lengths of the input arrays.
6 length_nums1, length_nums2 = len(nums1), len(nums2)
7
8 # Initialize the DP table with all values set to 0.
9 # The table dimensions will be (length_nums1 + 1) x (length_nums2 + 1).
10 dp_table = [[0] * (length_nums2 + 1) for _ in range(length_nums1 + 1)]
11
12 # Variable to hold the length of the longest common subarray.
13 max_length = 0
14
15 # Loop through each element in nums1.
16 for i in range(1, length_nums1 + 1):
17 # Loop through each element in nums2.
18 for j in range(1, length_nums2 + 1):
19 # Check if the elements at the current indices are the same.
20 if nums1[i - 1] == nums2[j - 1]:
21 # If they are, update the DP table by adding 1 to the value
22 # from the previous indices in both nums1 and nums2.
23 dp_table[i][j] = dp_table[i - 1][j - 1] + 1
24 # Update the max_length if a longer common subarray is found.
25 max_length = max(max_length, dp_table[i][j])
26
27 # Return the length of the longest common subarray.
28 return max_length
29
1// Class name Solution indicates that this is a solution to a problem.
2class Solution {
3
4 // Method findLength returns the length of the longest common subarray between two arrays.
5 public int findLength(int[] nums1, int[] nums2) {
6 // m and n store the lengths of the two input arrays nums1 and nums2 respectively.
7 int m = nums1.length;
8 int n = nums2.length;
9
10 // Create a 2D array 'dp' to store the lengths of common subarrays.
11 int[][] dp = new int[m + 1][n + 1];
12
13 // Variable 'maxLen' keeps track of the maximum length of common subarrays found so far.
14 int maxLen = 0;
15
16 // Iterate over the elements of nums1 and nums2.
17 for (int i = 1; i <= m; ++i) {
18 for (int j = 1; j <= n; ++j) {
19 // Check if elements from both arrays match.
20 if (nums1[i - 1] == nums2[j - 1]) {
21
22 // If they match, increment the value from the previous diagonal element by 1.
23 dp[i][j] = dp[i - 1][j - 1] + 1;
24
25 // Update 'maxLen' if the current length of the common subarray is greater.
26 maxLen = Math.max(maxLen, dp[i][j]);
27 }
28 // If elements do not match, the length of common subarray is 0 (by default in Java).
29 }
30 }
31
32 // Return the maximum length of common subarray found.
33 return maxLen;
34 }
35}
36
1#include <vector>
2#include <algorithm> // Include library for std::max
3
4using std::vector;
5using std::max;
6
7class Solution {
8public:
9 int findLength(vector<int>& nums1, vector<int>& nums2) {
10 // Size of the input vectors
11 int sizeNums1 = nums1.size();
12 int sizeNums2 = nums2.size();
13
14 // Create a 2D vector to store the length of longest common subarray ending at i-1 and j-1
15 vector<vector<int>> dp(sizeNums1 + 1, vector<int>(sizeNums2 + 1));
16
17 // Initialize answer to keep track of the max length of common subarray found so far
18 int maxLength = 0;
19
20 // Iterate over nums1 and nums2 vectors
21 for (int i = 1; i <= sizeNums1; ++i) {
22 for (int j = 1; j <= sizeNums2; ++j) {
23 // If elements match, extend the length of the common subarray
24 if (nums1[i - 1] == nums2[j - 1]) {
25 dp[i][j] = dp[i - 1][j - 1] + 1;
26
27 // Update maxLength with the largest length found
28 maxLength = max(maxLength, dp[i][j]);
29 }
30 // No need to handle the else case explicitly, as the dp array is initialized to 0s
31 }
32 }
33
34 // Return the maximum length of common subarray found
35 return maxLength;
36 }
37};
38
1function findLength(nums1: number[], nums2: number[]): number {
2 // Get the lengths of both input arrays.
3 const lengthNums1 = nums1.length;
4 const lengthNums2 = nums2.length;
5
6 // Initialize a 2D array 'dp' (dynamic programming table) with zeros.
7 // The table will store lengths of common subarrays.
8 const dp: number[][] = Array.from({ length: lengthNums1 + 1 }, () => new Array(lengthNums2 + 1).fill(0));
9
10 // Variable to keep track of the maximum length of common subarray found so far.
11 let maxLength = 0;
12
13 // Iterate over both arrays to fill the dynamic programming table.
14 for (let i = 1; i <= lengthNums1; ++i) {
15 for (let j = 1; j <= lengthNums2; ++j) {
16 // When elements at the current position in both arrays match,
17 // increment the value by 1 from the diagonally previous.
18 if (nums1[i - 1] === nums2[j - 1]) {
19 dp[i][j] = dp[i - 1][j - 1] + 1;
20 // Update maxLength if a longer common subarray is found.
21 maxLength = Math.max(maxLength, dp[i][j]);
22 }
23 }
24 }
25
26 // Return the maximum length of the common subarray.
27 return maxLength;
28}
29
Time and Space Complexity
The given code implements a dynamic programming approach to find the length of the longest common subsequence between two arrays nums1
and nums2
.
Time Complexity
The time complexity of the code is O(m * n)
, where m
is the length of nums1
and n
is the length of nums2
. This is because the code uses two nested loops, each iterating up to the length of the respective arrays. For each pair of indices (i, j)
the code performs a constant amount of work.
Space Complexity
The space complexity of the code is also O(m * n)
because it creates a 2D list f
of size (m + 1) * (n + 1)
to store the lengths of common subsequences for each index pair (i, j)
. This 2D list is required to remember the results for all subproblems, which is a typical requirement of dynamic programming approaches.
In summary:
- Time Complexity:
O(m * n)
- Space Complexity:
O(m * n)
Learn more about how to find time and space complexity quickly using problem constraints.
How many times is a tree node visited in a depth first search?
Recommended Readings
Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
https algomonster s3 us east 2 amazonaws com cover_photos stack svg Sliding Window Maximum Monotonic Stack We have an array and a sliding window defined by a start index and an end index The sliding window moves from left of the array to right There are always k elements in
Want a Structured Path to Master System Design Too? Donāt Miss This!