#1035
Uncrossed Lines
specialist · 625 · lc medium +29 · verified · 65.1% accepted · 3,967 likes · top 69%
Description
Write integer values from nums1 and nums2 on two separate horizontal lines (in the given order). You may draw a straight line connecting nums1[i] to nums2[j] whenever nums1[i] == nums2[j], provided it does not cross any other connecting line.
Return the maximum number of non-crossing connecting lines.
Example 1:
Input: nums1 = [1,4,2], nums2 = [1,2,4]
Output: 2
Explanation: We can draw 2 uncrossed lines as in the diagram.
We cannot draw 3 uncrossed lines, because the line from nums1[1] = 4 to nums2[2] = 4 will intersect the line from nums1[2]=2 to nums2[1]=2.
Example 2:
Input: nums1 = [2,5,1,2,5], nums2 = [10,5,2,1,5,2]
Output: 3
Example 3:
Input: nums1 = [1,3,7,1,7,5], nums2 = [1,9,2,5,1]
Output: 2
Code
1
2
3