Leetcode 1035. Uncrossed Lines

Problem Explanation:

This problem is all about finding the maximum number of uncrossed lines between two arrays of integers where a line connects two numbers only if they are equal. An important condition is that the lines should not intersect with each other, considering this we cannot count a number more than one time because it will cause an intersection in between lines.

We can use a dynamic programming approach to solve this problem. The idea is to fill a 2D DP table in such a way that dp[i][j] will give the maximum number of uncrossed lines between nums1[0,1,2.....i] and nums2[0,1,2....j].

Let's walk through an example:

Let array A = [1,4,2] and B = [1,2,4]

Here, the numbers 1 and 4 can be connected without any intersections. Hence, a maximum of 2 lines can be formed.

Solution In Python:

1
2python
3class Solution:
4  def maxUncrossedLines(self, nums1, nums2):
5    m = len(nums1)
6    n = len(nums2)
7    dp = [[0 for j in range(n+1)] for i in range(m+1)]
8
9    for i in range(1, m+1):
10      for j in range(1, n+1):
11        if nums1[i-1] == nums2[j-1]:
12          dp[i][j] = dp[i-1][j-1] + 1
13        else:
14          dp[i][j] = max(dp[i-1][j], dp[i][j-1])
15
16    return dp[m][n]

Solution In Java:

1
2java
3class Solution {
4    public int maxUncrossedLines(int[] nums1, int[] nums2) {
5        int m = nums1.length;
6        int n = nums2.length;
7        int[][] dp = new int[m+1][n+1];
8
9        for (int i=1; i<=m; i++) {
10            for (int j=1; j<=n; j++) {
11                if (nums1[i-1] == nums2[j-1]) {
12                    dp[i][j] = dp[i-1][j-1] + 1;
13                } else {
14                    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
15                }
16            }
17        }
18
19        return dp[m][n];
20    }
21}

Solution In JavaScript:

1
2javascript
3var maxUncrossedLines = function(nums1, nums2) {
4    let m = nums1.length;
5    let n = nums2.length;
6    let dp = Array(m+1).fill().map(() => Array(n+1).fill(0));
7
8    for (let i=1; i<=m; i++) {
9        for (let j=1; j<=n; j++) {
10            if (nums1[i-1] == nums2[j-1]) {
11                dp[i][j] = dp[i-1][j-1] + 1;
12            } else {
13                dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
14            }
15        }
16    }
17
18    return dp[m][n];
19};

Solution In C++:

1
2c++
3class Solution {
4public:
5    int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
6        int m = nums1.size();
7        int n = nums2.size();
8
9        vector<vector<int>> dp(m+1, vector<int>(n+1));
10
11        for (int i=1; i<=m; i++) {
12            for (int j=1; j<=n; j++) {
13                if (nums1[i-1] == nums2[j-1]) {
14                    dp[i][j] = dp[i-1][j-1] + 1;
15                } else {
16                    dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
17                }
18            }
19        }
20
21        return dp[m][n];
22    }
23};

Solution In C#:

1
2csharp
3public class Solution {
4    public int MaxUncrossedLines(int[] nums1, int[] nums2) {
5        int m = nums1.Length;
6        int n = nums2.Length;
7
8        int[,] dp = new int[m+1, n+1];
9
10        for (int i=1; i<=m; i++) {
11            for (int j=1; j<=n; j++) {
12                if (nums1[i-1] == nums2[j-1]) {
13                    dp[i, j] = dp[i-1, j-1] + 1;
14                } else {
15                    dp[i, j] = Math.Max(dp[i-1, j], dp[i, j-1]);
16                }
17            }
18        }
19
20        return dp[m, n];
21    }
22}

In all the above solutions, a 2D DP array is used to store the maximum number of uncrossed lines between two subarrays of nums1 and nums2. The solutions iterate through the two input arrays and if a same number is found then it's considered as a uncrossed line thus adding 1 to the total count of uncrossed lines, otherwise they find the maximum number of uncrossed lines by either considering the previous element of nums1 or the previous element of nums2. Finally, the maximum number of uncrossed lines are returned as the solution.## Complexity Analysis and Conclusion

The time complexity for all the solutions is O(n*m), where n and m are the sizes of the input arrays. This is because we are iterating once over each element of the first array and for each of these iterations, we are iterating over the entire second array.

The space complexity is also O(n*m) as we are creating a 2-dimensional dp array of size n*m.

These solutions work well for medium-sized input arrays. If the input size is huge, there might be some performance degradation due to the large size of 2-dimensional dp array.

From the solutions above, the problem can be resolved using various popular programming languages like Python, Java, JavaScript, C++, and C#. Each of these solutions basically does the same thing but with different language syntax.

In conclusion, the important part of solving this problem is understanding how dynamic programming can be used to find the maximum number of uncrossed lines between two arrays. The combination of using a dynamic programming table to keep track of the maximum number of lines and understanding how to update the table as you iterate through the arrays is key to solving this problem. And beyond being a coding problem, this also demonstrates how dynamic programming can be used to simplify solving complex problems.