## # 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=4 to B=4 will intersect the line from A=2 to B=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
for i in range(len(A)):
for j in range(len(B)):
if A[i] == B[j]:
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)):
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 - line1) * (line2 - line1) <= 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]
``````

Approach 1:

Approach 2: