LeetCode 1035. Uncrossed Lines Solution in Java, C++, Python & More | Explanation + Code

Description

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

Solutions

Solution 1: Dynamic Programming

We define f[i][j] to represent the maximum number of connections between the first i numbers of nums1 and the first j numbers of nums2. Initially, f[i][j] = 0, and the answer is f[m][n].

When nums1[i-1] = nums2[j-1], we can add a connection based on the first i-1 numbers of nums1 and the first j-1 numbers of nums2. In this case, f[i][j] = f[i-1][j-1] + 1.

When nums1[i-1] ≠ nums2[j-1], we either solve based on the first i-1 numbers of nums1 and the first j numbers of nums2, or solve based on the first i numbers of nums1 and the first j-1 numbers of nums2, taking the maximum of the two. That is, f[i][j] = max(f[i-1][j], f[i][j-1]).

Finally, return f[m][n].

The time complexity is O(m × n), and the space complexity is O(m × n). Here, m and n are the lengths of nums1 and nums2, respectively.

PythonJavaC++GoTypeScriptJavaScript

class Solution: def maxUncrossedLines(self, nums1: List[int], nums2: List[int]) -> int: m, n = len(nums1), len(nums2) f = [[0] * (n + 1) for _ in range(m + 1)] for i, x in enumerate(nums1, 1): for j, y in enumerate(nums2, 1): if x == y: f[i][j] = f[i - 1][j - 1] + 1 else: f[i][j] = max(f[i - 1][j], f[i][j - 1]) return f[m][n](code-box)

class Solution { public int maxUncrossedLines(int[] nums1, int[] nums2) { int m = nums1.length, n = nums2.length; int[][] f = 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]) { f[i][j] = f[i - 1][j - 1] + 1; } else { f[i][j] = Math.max(f[i - 1][j], f[i][j - 1]); } } } return f[m][n]; } }(code-box)

class Solution { public: int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) { int m = nums1.size(), n = nums2.size(); int f[m + 1][n + 1]; memset(f, 0, sizeof(f)); for (int i = 1; i <= m; ++i) { for (int j = 1; j <= n; ++j) { if (nums1[i - 1] == nums2[j - 1]) { f[i][j] = f[i - 1][j - 1] + 1; } else { f[i][j] = max(f[i - 1][j], f[i][j - 1]); } } } return f[m][n]; } };(code-box)

func maxUncrossedLines(nums1 []int, nums2 []int) int { m, n := len(nums1), len(nums2) f := make([][]int, m+1) for i := range f { f[i] = make([]int, n+1) } for i := 1; i <= m; i++ { for j := 1; j <= n; j++ { if nums1[i-1] == nums2[j-1] { f[i][j] = f[i-1][j-1] + 1 } else { f[i][j] = max(f[i-1][j], f[i][j-1]) } } } return f[m][n] }(code-box)

function maxUncrossedLines(nums1: number[], nums2: number[]): number { const m = nums1.length; const n = nums2.length; const f: number[][] = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0)); for (let i = 1; i <= m; ++i) { for (let j = 1; j <= n; ++j) { if (nums1[i - 1] === nums2[j - 1]) { f[i][j] = f[i - 1][j - 1] + 1; } else { f[i][j] = Math.max(f[i - 1][j], f[i][j - 1]); } } } return f[m][n]; }(code-box)

/** * @param {number[]} nums1 * @param {number[]} nums2 * @return {number} */ var maxUncrossedLines = function (nums1, nums2) { const m = nums1.length; const n = nums2.length; const f = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0)); for (let i = 1; i <= m; ++i) { for (let j = 1; j <= n; ++j) { if (nums1[i - 1] === nums2[j - 1]) { f[i][j] = f[i - 1][j - 1] + 1; } else { f[i][j] = Math.max(f[i - 1][j], f[i][j - 1]); } } } return f[m][n]; };(code-box)