Leetcode 718: Maximum Length of Repeated Subarray
Given two integer arrays
nums1
and nums2
, your task is to find the maximum length of a contiguous subarray that appears in both arrays.Problem
Approach
Steps
Complexity
Input: The input consists of two arrays `nums1` and `nums2` of integers.
Example: nums1 = [4, 5, 6, 7, 8], nums2 = [1, 2, 3, 4, 5]
Constraints:
• 1 <= nums1.length, nums2.length <= 1000
• 0 <= nums1[i], nums2[i] <= 100
Output: Return the maximum length of a contiguous subarray that appears in both `nums1` and `nums2`.
Example: 2
Constraints:
• The result should be a non-negative integer representing the length of the longest common subarray.
Goal: To compute the maximum length of a contiguous subarray that appears in both arrays using dynamic programming.
Steps:
• Create a 2D array `dp` where `dp[i][j]` represents the length of the longest common subarray ending at `nums1[i-1]` and `nums2[j-1]`.
• If `nums1[i-1] == nums2[j-1]`, then `dp[i][j] = dp[i-1][j-1] + 1`.
• Track the maximum value in the `dp` array during the iteration.
Goal: The solution should efficiently handle large inputs up to 1000 elements in both arrays.
Steps:
• The input arrays `nums1` and `nums2` have lengths up to 1000.
• Each element in `nums1` and `nums2` is between 0 and 100.
Assumptions:
• The input arrays will contain non-negative integers.
• The length of the arrays is guaranteed to be at least 1.
• Input: nums1 = [4, 5, 6, 7, 8], nums2 = [1, 2, 3, 4, 5]
• Explanation: The longest common subarray is [4, 5], which has a length of 2.
• Input: nums1 = [1, 2, 3, 4], nums2 = [2, 3, 4, 5]
• Explanation: The longest common subarray is [2, 3, 4], which has a length of 3.
Approach: The problem can be solved using dynamic programming to efficiently calculate the longest common subarray.
Observations:
• We need to keep track of the common subarrays between `nums1` and `nums2`.
• Dynamic programming will help us store the results of overlapping subproblems and avoid redundant calculations.
Steps:
• Initialize a 2D array `dp` with dimensions `(n1+1) x (n2+1)` where `n1` and `n2` are the lengths of `nums1` and `nums2` respectively.
• Iterate through both arrays. For each pair of elements `nums1[i-1]` and `nums2[j-1]`, if they match, update `dp[i][j]` as `dp[i-1][j-1] + 1`.
• Track the maximum value in the `dp` array, which will give the length of the longest common subarray.
Empty Inputs:
• If one of the arrays is empty, the result should be 0.
Large Inputs:
• Ensure that the solution works efficiently for large arrays with lengths up to 1000.
Special Values:
• Handle cases where all elements in the arrays are the same.
Constraints:
• Handle cases where no common subarray exists, in which case the result will be 0.
int findLength(vector<int>& nums1, vector<int>& nums2) {
int n1 = nums1.size(), n2 = nums2.size();
vector<vector<int>> dp(n1 + 1, vector<int>(n2 + 1));
for(int i = 0; i < n1 + 1; i++) dp[i][0] = 0;
for(int i = 0; i < n2 + 1; i++) dp[0][i] = 0;
// dp[0][0] = 0;
// subseq - !subarr
int mx = 0;
for(int i = 1; i < n1 + 1; i++)
for(int j = 1; j < n2 + 1; j++) {
if (nums1[i - 1] == nums2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
mx = max(mx, dp[i][j]);
}
}
return mx;
}
1 : Function Declaration
int findLength(vector<int>& nums1, vector<int>& nums2) {
Define the function 'findLength' that takes two vectors of integers 'nums1' and 'nums2' and returns an integer representing the maximum length of a common subarray.
2 : Variable Initialization
int n1 = nums1.size(), n2 = nums2.size();
Initialize two variables, 'n1' and 'n2', to store the sizes of 'nums1' and 'nums2', respectively.
3 : Array Initialization
vector<vector<int>> dp(n1 + 1, vector<int>(n2 + 1));
Initialize a 2D vector 'dp' with dimensions (n1+1) by (n2+1), where each entry will store the length of the common subarray ending at that position.
4 : Base Case Initialization
Base cases for dynamic programming are initialized in the following steps. The first row and first column of the DP table will be set to zero.
5 : Filling DP Table - Row Initialization
for(int i = 0; i < n1 + 1; i++) dp[i][0] = 0;
Set the first column of the DP table to zero since there is no common subarray with an empty second array.
6 : Filling DP Table - Column Initialization
for(int i = 0; i < n2 + 1; i++) dp[0][i] = 0;
Set the first row of the DP table to zero since there is no common subarray with an empty first array.
7 : Comment
// dp[0][0] = 0;
This line is a redundant initialization since dp[0][0] is already set to 0 in the previous loops.
8 : Dynamic Programming Loop Start
int mx = 0;
Initialize 'mx' to store the maximum length of the common subarray found during the iterations.
9 : Outer Loop - Iterating Over nums1
for(int i = 1; i < n1 + 1; i++)
Start the outer loop to iterate over each element of 'nums1', from index 1 to n1.
10 : Inner Loop - Iterating Over nums2
for(int j = 1; j < n2 + 1; j++) {
Start the inner loop to iterate over each element of 'nums2', from index 1 to n2.
11 : Condition Check - Matching Elements
if (nums1[i - 1] == nums2[j - 1]) {
Check if the elements at the current indices of 'nums1' and 'nums2' match. If they do, the common subarray is extended.
12 : DP Update - Matching Elements
dp[i][j] = dp[i - 1][j - 1] + 1;
If the elements match, update the DP table by adding 1 to the value from the previous diagonal entry, representing the length of the common subarray ending at that point.
13 : Max Length Update
mx = max(mx, dp[i][j]);
Update 'mx' to store the maximum length of the common subarray found so far.
14 : Return Maximum Length
return mx;
Return the maximum length of the common subarray found, stored in 'mx'.
Best Case: O(n1 * n2)
Average Case: O(n1 * n2)
Worst Case: O(n1 * n2)
Description: The time complexity is quadratic due to the two nested loops iterating over both arrays.
Best Case: O(n1 * n2)
Worst Case: O(n1 * n2)
Description: The space complexity is quadratic because we are using a 2D array to store the results.
LeetCode Solutions Library / DSA Sheets / Course Catalog |
---|
comments powered by Disqus