Uncrossed Lines Python Solution with Tests

Tested Python solution for LeetCode 1035 with 12 pytest cases. Generate a practice environment with lcpy.

LeetCode 1035, Medium. Topics: Array, Dynamic Programming. View on LeetCode.

Generate this problem as a practice environment: tested reference solution, 12 parametrized pytest cases, and a playground notebook:

lcpy gen -n 1035   # by problem number
lcpy gen -s uncrossed_lines   # by problem name

​

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 (non-horizontal) line.

Note that a connecting line cannot intersect even at the endpoints (i.e., each number can only belong to one connecting line).

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

​

Examples

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.

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

​

Constraints

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

​

Solution

Reference implementation from solution.py on GitHub, full suite in test_solution.py:

class Solution:
    # Time: O(m * n)
    # Space: O(min(m, n))
    def max_uncrossed_lines(self, nums1: list[int], nums2: list[int]) -> int:
        if len(nums2) < len(nums1):
            nums1, nums2 = nums2, nums1
        prev = [0] * (len(nums2) + 1)
        for a in nums1:
            curr = [0] * (len(nums2) + 1)
            for j, b in enumerate(nums2):
                if a == b:
                    curr[j + 1] = prev[j] + 1
                else:
                    curr[j + 1] = max(prev[j + 1], curr[j])
            prev = curr
        return prev[-1]

​

Complexity

Time	Space
O(m * n)	O(min(m, n))

​

Tags

NeetCode All.