#LeetCode: Uncrossed Lines

Also Check: Solutions Of May LeetCoding Challenge (2020)

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

Now, we may draw connecting lines: a straight line connecting two numbers A[i] and B[j] such that:
A[i] == B[j];
The line we draw does not intersect any other connecting (non-horizontal) line.
Note that a connecting lines cannot intersect even at the endpoints: each number can only belong to one connecting 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

Note:
1 <= A.length <= 500
1 <= B.length <= 500
1 <= A[i], B[i] <= 2000

FYI, this problem is quite similar to Leetcode's Longest Common Subsequence

Algorithm 1

GIT URL: Java Solution of Leet Code's Uncrossed Lines problem

Java Solution:

Algorithm 2

GIT URL: Another Java Solution of Leet Code's Uncrossed Lines problem

Another way to solve Uncrossed Lines using Memo table (I had used this approach to solve Leetcode's Longest Common Subsequence problem). Here is the algorithm, which we are going to follow:

if(A[m]==B[n])
   1+T(m-1, n-1);
else
   max(T(m-1,n), T(m, n-1);

1). We will create a memo table: T[A.length+1][B.length+1]
T[0][i] and T[i][0] will be populated with zero, i.e first row and first column will be zero in memo table.
2). Now we will start iterating.
3). If the value of A[m] is equal to B[n], then we will take value at the left top diagonal position i.e T(m-1, n-1), increment it with 1 and set that value at T[m][n] position.
4). Else we will set the value at T[m][n] position with value at the top i.e T(m-1,n) OR left position i.e T(m, n-1), which ever is higher.
5). At the end of the iteration the value at the last row and last column of the memo table would be the number of Uncrossed Lines.

Let us understand by taking an example:
A = [1,4,2], B = [1,2,4]

Java Solution

ALSO CHECK: Other LeetCode Solutions in Java

-K Himaanshu Shuklaa.