Uncrossed Lines
You are given two integer arrays nums1 and nums2. We write the integers of nums1 and nums2 (in the order they are given) on two separate horizontal lines.
We may draw connecting lines: a straight line connecting nums1[i] and nums2[j] such that nums1[i] == nums2[j], and the line we draw does not intersect any other connecting lines.
Return the maximum number of connecting lines we can draw in this way.
Examples
Input: [[1,4,2],[1,2,4]]
Output: 2
Input: [[2,5,1,2,5],[10,5,2,1,5,2]]
Output: 3
Hints
Consider transforming this problem into finding the longest common subsequence (LCS) between `nums1` and `nums2`, where the order of elements must be preserved to avoid line intersections.
To optimize the LCS approach, observe that only matching elements between `nums1` and `nums2` matter. You can preprocess the arrays to track the indices of each value in `nums2` and then use dynamic programming to count valid connections.
The problem reduces to finding the maximum number of non-overlapping matches between `nums1` and `nums2` where the matches are in increasing order of indices in both arrays. This can be solved using a greedy approach with binary search after preprocessing.
Related Problems
Uncrossed Lines
You are given two integer arrays `nums1` and `nums2`. We write the integers of `nums1` and `nums2` (in the order they are given) on two separate horizontal lines.