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.
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.
