1035. Uncrossed Lines LeetCode Solution

Last updated: February 21, 2025

In this guide, you will get 1035. Uncrossed Lines LeetCode Solution with the best time and space complexity. The solution to Uncrossed Lines problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Uncrossed Lines solution in C++
Uncrossed Lines solution in Java
Uncrossed Lines solution in Python
Additional Resources

1035. Uncrossed Lines LeetCode Solution image

Problem Statement of Uncrossed Lines

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: a straight line connecting two numbers nums1[i] and nums2[j] such that:

nums1[i] == nums2[j], and
the line we draw does not intersect any other connecting (non-horizontal) line.

Note that a connecting line cannot intersect even at the endpoints (i.e., 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: nums1 = [1,4,2], nums2 = [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 nums1[1] = 4 to nums2[2] = 4 will intersect the line from nums1[2]=2 to nums2[1]=2.

Example 2:

Input: nums1 = [2,5,1,2,5], nums2 = [10,5,2,1,5,2]
Output: 3

Example 3:

Input: nums1 = [1,3,7,1,7,5], nums2 = [1,9,2,5,1]
Output: 2

Constraints:

1 <= nums1.length, nums2.length <= 500
1 <= nums1[i], nums2[j] <= 2000

Complexity Analysis

Time Complexity: O(mn)
Space Complexity: O(mn)

1035. Uncrossed Lines LeetCode Solution in C++

class Solution {
 public:
  int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
    const int m = nums1.size();
    const int n = nums2.size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1));

    for (int i = 1; i <= m; ++i)
      for (int j = 1; j <= n; ++j)
        dp[i][j] = nums1[i - 1] == nums2[j - 1]
                       ? dp[i - 1][j - 1] + 1
                       : max(dp[i - 1][j], dp[i][j - 1]);

    return dp[m][n];
  }
};
/* code provided by PROGIEZ */

1035. Uncrossed Lines LeetCode Solution in Java

class Solution {
  public int maxUncrossedLines(int[] nums1, int[] nums2) {
    final int m = nums1.length;
    final 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)
        dp[i][j] = nums1[i - 1] == nums2[j - 1] ? dp[i - 1][j - 1] + 1
                                                : Math.max(dp[i - 1][j], dp[i][j - 1]);

    return dp[m][n];
  }
}
// code provided by PROGIEZ

1035. Uncrossed Lines LeetCode Solution in Python

class Solution:
  def maxUncrossedLines(self, nums1: list[int], nums2: list[int]) -> int:
    m = len(nums1)
    n = len(nums2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(1, m + 1):
      for j in range(1, n + 1):
        dp[i][j] = (dp[i - 1][j - 1] + 1
                    if nums1[i - 1] == nums2[j - 1]
                    else max(dp[i - 1][j], dp[i][j - 1]))

    return dp[m][n]
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents