# 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: