Sponsored
Sponsored
This approach uses a dynamic programming (DP) solution where we maintain a 2D array called dp. The element dp[i][j] represents the maximum number of lines that can be drawn without crossing up to the i-th element of nums1 and the j-th element of nums2.
The DP formulation is based on: if nums1[i] == nums2[j], then dp[i][j] = dp[i-1][j-1] + 1. Otherwise, dp[i][j] = max(dp[i-1][j], dp[i][j-1]).
The final answer is found in dp[m][n], where m and n are the lengths of nums1 and nums2 respectively. This approach runs in O(m * n) time complexity and uses O(m * n) space.
Time Complexity: O(m * n), where m and n are the lengths of nums1 and nums2.
Space Complexity: O(m * n), for the dp array.
1#include <vector>
2#include <iostream>
3using namespace std;
4
5int maxUncrossedLines(vector<int>& A, vector<int>& B) {
6 int m = A.size(), n = B.size();
7 vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
8 for (int i = 1; i <= m; ++i) {
9 for (int j = 1; j <= n; ++j) {
10 if (A[i - 1] == B[j - 1])
11 dp[i][j] = dp[i - 1][j - 1] + 1;
12 else
13 dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
14 }
15 }
16 return dp[m][n];
17}
18
19int main() {
20 vector<int> nums1 = {1, 4, 2};
21 vector<int> nums2 = {1, 2, 4};
22 cout << "Output: " << maxUncrossedLines(nums1, nums2) << endl;
23 return 0;
24}The C++ version makes use of the vector class to create a 2D DP table. It uses a similar nested loop strategy as the C version to fill up the table according to the relationship between the current elements of nums1 and nums2. At each step, it checks if the elements are the same and updates the DP table accordingly to maintain the maximum number of lines.
This approach is an optimization of the basic dynamic programming solution by reducing space complexity. Instead of utilizing a 2D array, we can use a single-dimensional array to store only the current and previous row information, thus reducing the space usage. This takes advantage of the fact that the current DP state depends only on the previous state, not all preceding states.
We maintain two 1D arrays, and they get updated in each iteration over the second array, resulting in reduced space complexity to O(min(m, n)).
Time Complexity: O(m * n), where m and n are the lengths of nums1 and nums2.
Space Complexity: O(min(m, n)), for the dp array.
The Pythonic pattern for reduced-space usage involves a single iterative array dp, which records ongoing state progress throughout the arrays. Element matching prompts state advancement, while non-matching elements rely on propagated maxima for determining sequence continuity.