# 1035. Uncrossed Lines

We write the integers of A and B (in the order they are given) on two separate horizontal lines.

Now, we may draw a straight line connecting two numbers A[i] and B[j] as long as A[i] == B[j], and the line we draw does not intersect any other connecting (non-horizontal) line.

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

Example 1:

Input: A = [1,4,2], B = [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 A[1]=4 to B[2]=4 will intersect the line from A[2]=2 to B[1]=2.

Example 2:

Input: A = [2,5,1,2,5], B = [10,5,2,1,5,2]
Output: 3

Example 3:

Input: A = [1,3,7,1,7,5], B = [1,9,2,5,1]
Output: 2

# Solution

Approach 1: brute force (TLE). Generate all linkable pairs, then backtracking for the largest subset where no pairs intersects with each other.

Approach 2: essentially the longest common subsequence problem -- use DP.

# Code (Python)

Approach 1:

    def maxUncrossedLines(self, A, B):
        # TLE
        # generate linkable pairs
        linkables = []
        for i in range(len(A)):
            for j in range(len(B)):
                if A[i] == B[j]:
                    linkables.append((i, j))
        if not linkables:
            return 0
        # backtracking for the largest subset where no pairs intersects with each other
        self.max_lines = 1
        self._find_max_lines([], 0, linkables, {})
        return self.max_lines
    
    def _find_max_lines(self, subset, index, linkables, overlap_cache):
        for i in range(index, len(linkables)):
            new_line = linkables[i]
            if not subset or all(not self._overlaps(existing_line, new_line, overlap_cache) for existing_line in subset):
                subset.append(new_line)
                self.max_lines = max(self.max_lines, len(subset)) # no base case; update max_lines as soon as new append is made
                self._find_max_lines(subset, i + 1, linkables, overlap_cache)
                subset.pop()
    
    def _overlaps(self, line1, line2, cache):
        if (line1, line2) in cache:
            return cache[(line1, line2)]
        if (line2, line1) in cache:
            return cache[(line2, line1)]
        cache[(line1, line2)] = ((line2[0] - line1[0]) * (line2[1] - line1[1]) <= 0)
        return cache[(line1, line2)]

Approach 2:

    def maxUncrossedLines(self, A, B):
        # essentially longest common subsequence problem: https://en.wikipedia.org/wiki/Longest_common_subsequence_problem
        # idea: DP. table[i][j] -- LCS of A[:i] and B[:j]
        table = [[0 for _ in range(len(B) + 1)] for _ in range(len(A) + 1)]
        for i in range(len(A) + 1):
            for j in range(len(B) + 1):
                if i == 0 or j == 0:
                    continue
                if A[i-1] == B[j-1]:
                    table[i][j] = table[i-1][j-1] + 1
                else:
                    table[i][j] = max(table[i][j-1], table[i-1][j])
        return table[-1][-1]
    
    def maxUncrossedLines(self, A, B):
        # DP with space optimization
        table = [0 for _ in range(len(B) + 1)]
        for i in range(1, len(A) + 1):
            for j in range(len(B), 0, -1): # backwards because we want to retain table[i-1][j-1]
                if A[i-1] == B[j-1]:
                    table[j] = table[j-1] + 1
            for j in range(1, len(B) + 1): # now forward to update the rest
                if A[i-1] != B[j-1]:
                    table[j] = max(table[j-1], table[j])
        return table[-1]

# Code (C++)

Approach 1:

Approach 2: