1. Problem Description

You are given two integer arrays nums1 and nums2.
We draw a line connecting nums1[i] and nums2[j] if and only if nums1[i] == nums2[j], and no two lines cross each other.

Your task is to return the maximum number of connecting lines that can be drawn between these arrays such that no two lines intersect.

Example:

Input: nums1 = [1, 4, 2], nums2 = [1, 2, 4]
Output: 2
Explanation: We can draw lines between 1 (nums1[0]) → 1 (nums2[0]) and 2 (nums1[2]) → 2 (nums2[1]).

---

2. Intuition and Relationship to Longest Common Subsequence (LCS)

This problem is conceptually similar to the Longest Common Subsequence (LCS) problem.

Why?

• You can connect numbers only if they are equal.
• Lines cannot cross, which means the order must be maintained — just like in a subsequence.

Therefore, the maximum number of uncrossed lines between the two arrays equals the length of their Longest Common Subsequence (LCS).

---

3. Dynamic Programming Approach

We will use Dynamic Programming (DP) to compute the LCS between nums1 and nums2.

Step 1: Define the DP State

Let dp[i][j] represent the maximum number of uncrossed lines that can be drawn between the first i elements of nums1 and the first j elements of nums2.

Step 2: Recurrence Relation

If nums1[i - 1] == nums2[j - 1]
→ we can connect them, so:

dp[i][j] = dp[i - 1][j - 1] + 1

Otherwise, we cannot connect them, so we take the maximum from either:

• skipping the current element from nums1 (dp[i - 1][j]), or
• skipping the current element from nums2 (dp[i][j - 1])

dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

Step 3: Base Case

If i == 0 or j == 0, then dp[i][j] = 0
(since no lines can be drawn with an empty array).

---

4. Algorithm

1. Initialize a 2D DP array of size (len(nums1)+1) × (len(nums2)+1) with zeros.
2. Iterate over i = 1 to nums1.length
   • For each j = 1 to nums2.length:
     • If elements match → dp[i][j] = dp[i-1][j-1] + 1
     • Else → dp[i][j] = max(dp[i-1][j], dp[i][j-1])
3. The final answer is stored in dp[nums1.length][nums2.length].

---

5. Dry Run Example

Let’s take:

nums1 = [1, 4, 2]
nums2 = [1, 2, 4]

i/j	0	1	2	3
0	0	0	0	0
1	0	1	1	1
2	0	1	1	1
3	0	1	2	2

Explanation:

• dp[1][1] = 1 → 1 matches 1
• dp[3][2] = 2 → subsequence [1, 2]
• dp[3][3] = 2 → no increase since 2 != 4

Final Answer = 2

---

6. Java Code Implementation

public class UncrossedLines {
    public int maxUncrossedLines(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        int[][] dp = new int[m + 1][n + 1];
        
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; 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 - 1][j], dp[i][j - 1]);
                }
            }
        }
        
        return dp[m][n];
    }

    public static void main(String[] args) {
        UncrossedLines solution = new UncrossedLines();
        int[] nums1 = {1, 4, 2};
        int[] nums2 = {1, 2, 4};
        System.out.println(solution.maxUncrossedLines(nums1, nums2)); // Output: 2
    }
}

---

7. Time and Space Complexity

• Time Complexity: O(m * n)
  We fill each cell in the DP table once.
• Space Complexity: O(m * n)
  We use a 2D array of size (m+1) × (n+1).

Optimization:
We can reduce space to O(min(m, n)) using a rolling 1D DP array since each state depends only on the previous row.

---

8. Summary

Concept	Explanation
Problem Type	Dynamic Programming
Core Idea	Same as Longest Common Subsequence (LCS)
DP State	dp[i][j] → max lines between first i elements of nums1 and first j of nums2
Recurrence	dp[i][j] = dp[i-1][j-1] + 1 if match, else max(dp[i-1][j], dp[i][j-1])
Complexity	Time: O(m*n), Space: O(m*n)