The link to the problem: https://leetcode.com/problems/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 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 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
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.
Thoughts:
The first question we need to solve is that —how to avoid lines intersecting with others but also connect lines as many as possible?
I didn’t come up with any solution at first. Hence, I just try how we “manually” find the connected lines without any intersections. Hope that we can find some pattern to follow so that we don’t need to use brute force to solve the problem.
The maximum number of lines we can get is when all the numbers in A are exactly the same as B.
For example, if we have two input arrays like:
1 2 3 4
| | | |
1 2 3 4If we swap 3 and 4 in A, it will be like:
1 2 4 3 1 2 4 3
| | / or | | \
1 2 3 4 1 2 3 4However, if we add one or more new numbers in either A or B, it will not change the fact that we AT LEAST can draw four lines (maybe we can draw more depends on the new numbers, but at least 4):
1 2 5 3 4 7
| \ | \
1 6 2 3 5 4So we can actually find a pattern of these connected lines, this question might be able to convert to “finding the common subsequence.” Since we only care about the order of the numbers that we want to connect, even if their positions in either array A or array B do not exactly match (i.e., the connected numbers don’t need to be contiguous or don’t need to be “subarray”).
As long as the order of the current connected number is later than the previous connected number, we won’t let those connected lines intersecting each other.
Code Logic:
Finding the Longest Common Subsequence between two words is actually a typical dynamic programming problem. You can skip here and scroll down to the bottom of this story to see the solution code.
I will also use some graphs to illustrate the idea after explaining the code logic.
The concept of dynamic programming is that we can use past knowledge so that we can solve future problems easier. Here, since we are trying to form the longest subsequence and a long subsequence is formed by many small subsequences, it is nice to record what’s the longest length of the subsequence that we can form when we end at a certain position i in array A and a certain position j in array B.
We will let dp[i][j] to be the maximum number of lines we can get when the numbers are in index 0 to i of A and in index 0 to j of B. i.e., dp[2][4] means the maximum number of lines we can connect the A[0], A[1], A[2] with B[0], B[1], B[2], B[3], and B[4].
The logic is that if we want to find the maximum number of lines we can connect when the numbers in A[0 … i] and B[0…j], we need to first check if A[i] can connect B[j] depends on the equivalence between them:
- If we can connect the numbers of A[i] and B[j] since they are the same number, then the number of lines we can connect when we reach these two points is 1 (i.e., current line) + the number of lines we can connect the numbers in A[0] to A[i-1] with the numbers in B[0] to B[j-1].
- If we cannot connect the numbers of A[i] and B[j], then we will just either ignore A[i] OR B[j] and see the number of lines how we can connect the rest of the two sides number when we ignore A[i] or B[j]. (i.e., A[0…i-1] and B[0…j] OR A[0…i] and B[0…j-1])
Below is the 4ms code (beats 94%) that using this logic:
public int maxUncrossedLines(int[] A, int[] B) {
int count = 0;
int m = A.length, n = B.length;
int[][] dp = new int[m][n];
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
if(i==0 || j==0)
{
if(A[i]==B[j])
dp[i][j] = 1;
else
{
if(j!=0)
dp[i][j] = dp[i][j-1];
else if(i!=0)
dp[i][j] = dp[i-1][j];
}
continue;
}
if(A[i]==B[j])
dp[i][j] = dp[i-1][j-1]+1;
else
dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]); }
}
return dp[m-1][n-1];
}
You will see that we need a lot of conditions when i = 0 or j=0 in case we are referencing the out of bound values. Hence, we can also “add one meaningless slot right before A[0] and B[0]”.
Hence, dp[i][j] now represents the maximum number of lines we can connect when we are connecting the numbers in A[0…i-1] with B[0…j-1].
Although the time complexity didn’t really improve, the code is now cleaner:
public int maxUncrossedLines(int[] A, int[] B) {
int count = 0;
int m = A.length, n = B.length;
int[][] dp = new int[m+1][n+1];
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
if(A[i-1]==B[j-1])
dp[i][j] = 1 + dp[i-1][j-1];
else
dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
}
}
return dp[m][n];
}👷If the above code still sounds confusing for you, let’s use an example to see why dynamic programming works when we have A=[9,6,5,8,7] and B=[9,6,6,7,5]:
🔧Step 0. First, we are going to build a dp table and store all the results that we have found. Since the empty slots are meaningless, there won’t be any connected lines between a meaningless number with any number. Hence, we will never traverse these dp[0][j] and dp[i][0].
🔧Step 1: Our first mission is going to assign values for dp[1][j]. i.e., We are going to find the maximum number of lines when A only has 1 number — 9️⃣ and B has 1~5 numbers — 9️⃣ 6️⃣ 6️⃣ 7️⃣ 5️⃣
When we are at dp[1][1], it means that we are going to find the number of lines when A has 1 number 9️⃣ and B only has 1 number 9️⃣.
Our first step is to check if the last number in A can connect with the last number in B. We found that these two numbers can be connected. Hence, the value of dp[1][1] is 1.
When we are at dp[1][2], we are going to check if we can connect 9️⃣ in A and 6️⃣ in B. Since we cannot, we are going to just remain what we have in dp[1][1]. And the same thing as the remaining numbers in B.
9
|
9 6 6 7 5
🔧Step 2: Now, we are going to assign values for dp[2][j]. i.e., We are going to find the maximum number of lines when A has 2 numbers — 9️⃣ 6️⃣ and B has 1~5 numbers — 9️⃣ 6️⃣ 6️⃣ 7️⃣ 5️⃣.
When we are at dp[2][1], it means that we are going to find the number of lines when A has 2 numbers 9️⃣ 6️⃣ and B only has 1 number 9️⃣. Since we cannot connect 6️⃣ and 9️⃣, we will just remain what we have in dp[1][1].
9 6
|
9Next, when we are at dp[2][2], we are going to see the number of lines we can connect when A has 2 numbers 9️⃣ 6️⃣and B has 2 numbers 9️⃣ 6️⃣. Now, we found that we can connect 6️⃣ and 6️⃣. Hence, we will see what’s the number of lines that if we ignore this pair of 6 in A and B. We found that there’s one line that we can match in the previous numbers. Hence, the value dp[2][2] is 2.
9 6
| |
9 6Next, when we are at dp[2][3], we are going to see the number of lines we can connect when A has 2 numbers 9️⃣ 6️⃣and B has 3 numbers 9️⃣ 6️⃣ 6️⃣. We found that 6️⃣ can connect with the 6️⃣(The second 6 in B). Hence, we will see what’s the number of lines that if we ignore this pair of 6 in A. We found that there’s one line that we can match in the previous numbers. Hence, the value dp[2][3] is 2.
9 6
| \
9 6 6Next, when we are at the remaining cells on dp[2][4], we are going to see the number of lines we can connect when A has 2 numbers 9️⃣ 6️⃣and B has 4 numbers 9️⃣ 6️⃣ 6️⃣ 7️⃣. We found that we cannot connect 6️⃣ in A and 7️⃣ in B. Hence, we are going to choose the maximum lines we can connect if A has 1 number and B has 4 numbers OR lines we can connect if A has 2 numbers and B has 3 numbers. We found that dp[2][3] is bigger, we will just use its value and the graph will actually look like the one below.
9 6
| \
9 6 6 7Same thing we are going to do at dp[2][5]:
9 6
| \
9 6 6 7 8
🔧Step 3. Now, we are going to assign values for dp[3][j]. i.e., We are going to find the maximum number of lines when A has 3 numbers — 9️⃣ 6️⃣ 5️⃣ and B has 1~5 numbers — 9️⃣ 6️⃣ 6️⃣ 7️⃣ 5️⃣.
When we traverse to dp[3][5], it means that we are going to see the number of lines that we can connect if A has 3 numbers and B has 5 numbers. Since we can connect 5️⃣ in A and 5️⃣ in B, we are going to check the situation if we ignore this pair of 5 in A and B. Hence, we will find that the final graph will be like the one below if we want to connect 5s.
9 6 5
| \ |
9 6 6 7 5 
🔧Step 4. Now, we are going to assign values for dp[4][j]. i.e., We are going to find the maximum number of lines when A has 4 numbers — 9️⃣ 6️⃣ 5️⃣ 8️⃣and B has 1~5 numbers — 9️⃣ 6️⃣ 6️⃣ 7️⃣ 5️⃣.
We cannot connect any new line if we include an 8️⃣ in A. Hence, the result of this row will be exactly the same as the previous step.
9 6 5 8
| \ |
9 6 6 7 5 
🔧Step 5. Now, we are going to assign values for dp[5][j]. i.e., We are going to find the maximum number of lines when A has 5 numbers — 9️⃣ 6️⃣ 5️⃣ 8️⃣ 7️⃣and B has 1~5 numbers — 9️⃣ 6️⃣ 6️⃣ 7️⃣ 5️⃣.
When we are at dp[5][4], we are going to find the number of lines when A has 5 numbers and B has 4 numbers. We found that we can connect the 7s in A and B. Hence, we are going to use the graph when we never add this pair of 7 in either A or B.
9 6 5 8 7
| \ |
9 6 6 7When we are at dp[5][5], we are going to find the number of lines when A and B both have 5 numbers. Since we cannot connect the last number in A with the last number in B, we will just see which graph we will get more lines if we ignore the last number in either A or B.
Hence, you can say that the graphs below can both be the final answer.
9 6 5 8 7 9 6 5 8 7
| \ | or | \ \
9 6 6 7 5 9 6 6 7 5
👷And that’s the end of the code. You will find the maximum number of lines is 3 for this example.
