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.
This JavaScript implementation uses arrays to form a dynamic programming 2D grid to map possible sequences of lines. The strategy involves iterating over each possible pair of indices between the two arrays, accumulating a higher score when equal elements are found, thus ensuring that the maximum number of uncrossed lines is calculated.
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.
1#include <stdio.h>
2#include <string.h>
3
4int maxUncrossedLines(int* A, int ASize, int* B, int BSize) {
5 if (ASize < BSize) return maxUncrossedLines(B, BSize, A, ASize);
6 int dp[BSize + 1];
7 memset(dp, 0, sizeof(dp));
8 for (int i = 1; i <= ASize; i++) {
9 int prev = 0;
10 for (int j = 1; j <= BSize; j++) {
11 int cur = dp[j];
12 if (A[i - 1] == B[j - 1])
13 dp[j] = prev + 1;
14 else
15 dp[j] = (dp[j] > dp[j - 1]) ? dp[j] : dp[j - 1];
16 prev = cur;
17 }
18 }
19 return dp[BSize];
20}
21
22int main() {
23 int nums1[] = {1, 4, 2};
24 int nums2[] = {1, 2, 4};
25 int result = maxUncrossedLines(nums1, 3, nums2, 3);
26 printf("Output: %d\n", result);
27 return 0;
28}By leveraging a single array dp of size equal to nums2, the solution benefits from reduced space usage. We keep track of the previous computed value using a temporary variable prev. For each element pair, we determine the longest line by either incrementing based on a match or preserving the maximum from prior positions.
Solve with full IDE support and test cases