Uncrossed Lines

The key idea

A line connects equal numbers, and lines cannot cross, so the connected pairs must keep their order in both lists. That is exactly the longest common subsequence of nums1 and nums2 — the answer is the LCS length.

Problem

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 two numbers nums1[i] and nums2[j] such that nums1[i] == nums2[j], and the line we draw does not intersect any other connecting line. Note that a connecting line cannot intersect even at the endpoints (each number can belong to at most one connecting line).

Return the maximum number of connecting lines we can draw in this way.

Constraints

1 <= nums1.length, nums2.length <= 500
1 <= nums1[i], nums2[j] <= 2000

Examples

Input: nums1 = [1,4,2], nums2 = [1,2,4] Output: 2

Input: nums1 = [2,5,1,2,5], nums2 = [10,5,2,1,5,2] Output: 3

Input: nums1 = [1,3,7,1,7,5], nums2 = [1,9,2,5,1] Output: 2

Complexity

Time: O(m*n) Space: O(m*n)

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →