Uncrossed Lines - Leetcode Solution

Problem:

You are given two integer arrays nums1 and nums2. We write the integers of nums1 and nums2 (in the order they are given) on two separate horizontal lines.

We may draw connecting lines between two numbers nums1[i] and nums2[j] as long as nums1[i] == nums2[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.

Solution:

Let's try to approach this problem using Dynamic Programming. We will first create a 2D array dp of size (nums1.length+1) * (nums2.length+1) and initialize each cell of dp with 0.

We will loop through nums1 and nums2 and fill the dp array by considering two cases:

1. If nums1[i] == nums2[j], then we can draw a connecting line between nums1[i] and nums2[j]. In this case, the value of dp[i][j] will be equal to the value of dp[i-1][j-1] + 1 (i.e. the maximum number of connecting lines we can draw without considering nums1[i] and nums2[j], plus 1 for the current connecting line).

2. If nums1[i] != nums2[j], then we cannot draw a connecting line between nums1[i] and nums2[j]. In this case, we have two options: either draw a connecting line between nums1[i] and some other number in nums2 or draw a connecting line between nums2[j] and some other number in nums1. We will choose the option that gives us the maximum number of connecting lines. The value of dp[i][j] will be equal to the maximum of dp[i][j-1] and dp[i-1][j].

Finally, we return the value of dp[nums1.length][nums2.length], which will give us the maximum number of connecting lines we can draw.

Here is the Java code for the same:

public int maxUncrossedLines(int[] nums1, int[] nums2) {
        int[][] dp = new int[nums1.length+1][nums2.length+1];
        for(int i=1;i<=nums1.length;i++){
            for(int j=1;j<=nums2.length;j++){
                if(nums1[i-1]==nums2[j-1]){
                    dp[i][j]=dp[i-1][j-1]+1;
                }else{
                    dp[i][j]= Math.max(dp[i][j-1],dp[i-1][j]);
                }
            }
        }
        return dp[nums1.length][nums2.length];
}

Time Complexity: O(mn), where m = nums1.length and n = nums2.length. Space Complexity: O(mn), where m = nums1.length and n = nums2.length.

Therefore, the time and space complexity of this solution is optimal.

1