1035. Uncrossed Lines

Problem Description

In this problem, we are given two arrays nums1 and nums2, and we are asked to find the maximum number of "uncrossed lines" that can be drawn connecting equal elements in the two arrays such that each line represents a pair of equal numbers and does not cross over (or intersect) any other line. A line connecting nums1[i] and nums2[j] can only be drawn if nums1[i] == nums2[j] and it doesn't intersect with other connecting lines. A line cannot intersect with others even at the endpoints, which means each number is used once at most in the connections.

Essentially, this is a problem of finding the maximum number of pairings between two sequences without any overlaps. The problem can also be thought of as finding the longest sequence of matching numbers between nums1 and nums2 taking the order of numbers in each list into account.

Intuition

The intuition for solving this problem comes from a classic dynamic programming challenge — the Longest Common Subsequence (LCS) problem. In the LCS problem, we aim to find the longest subsequence common to two sequences which may be found in different orders within the two sequences. This problem is similar, as connecting lines between matching numbers creates a sequence of matches.

To solve the LCS problem, we can construct a two-dimensional dp (short for dynamic programming) array, where dp[i][j] represents the length of the longest common subsequence between nums1[:i] and nums2[:j] — that is, up to the i-th element in nums1 and j-th element in nums2. We initialize a matrix with zeros, where the first row and first column represent the base case where one of the sequences is empty (no common elements).

The following relation is used to fill the dp matrix:

• If nums1[i - 1] == nums2[j - 1], we have found a new common element. We take the value from the top-left diagonal dp[i - 1][j - 1] and add 1 to it because we have found a match, and add it to the current dp[i][j].
• If nums1[i - 1] != nums2[j - 1], no new match is found, so we take the maximum of the previous subproblem solutions. That is, we check whether the longest sequence is obtained by including one more element from nums1 (use the value in dp[i - 1][j]) or by including one more element from nums2 (use the value in dp[i][j - 1]).

The dynamic programming approach ensures that we do not recount any sequence and that we build our solution in a bottom-up manner, considering all possible matches from the simplest case (empty sequences) up to the full sequences. The final answer to the maximum number of uncrossed lines is given by dp[m][n], which is the value for the full length of both nums1 and nums2.

Learn more about Dynamic Programming patterns.

Solution Approach

The solution uses a dynamic programming approach to solve the problem efficiently. The key concept here is to build up the solution using previously computed results, avoiding redundant computations.

Here are the steps outlining the implementation details:

• We first initialize a two-dimensional array dp with dimensions (m+1) x (n+1), where m is the length of nums1 and n is the length of nums2. The array is initialized with zeros. This array will help us store the lengths of the longest common subsequences found up to each pair of indices (i, j).

• The dp array is filled up row by row and column by column starting at index 1, because the 0-th row and column represent the base case where either of the input sequences is empty.

• For every pair of indices i from 1 to m and j from 1 to n, we check if the elements nums1[i - 1] and nums2[j - 1] match.

  • If nums1[i - 1] == nums2[j - 1], this means that we can extend a common subsequence found up to dp[i-1][j-1]. We add 1 to the value of dp[i-1][j-1] and store it in dp[i][j]. This represents extending the length of the current longest common subsequence by 1.

    • Mathematically, it is represented as:

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

  • If nums1[i - 1] != nums2[j - 1], this means that the current elements do not match, so we cannot extend the subsequence by including both of these elements. Instead, we take the maximum value between dp[i-1][j] and dp[i][j-1].

    • This means we are either including the i-th element from nums1 and not the j-th element from nums2, or vice versa, depending on which option provides a longer subsequence so far.

    • Mathematically, it is represented as:

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

• After completing the filling of the dp matrix, the value of dp[m][n] will give us the maximum number of connecting lines we can draw. This represents the length of the longest common subsequence between nums1 and nums2.

By using dynamic programming, the algorithm ensures that we are only computing the necessary parts of the solution space and building upon them to find the optimal solution to the original problem.

Example Walkthrough

Let's illustrate the solution approach with small example arrays nums1 = [2, 5, 1] and nums2 = [5, 2, 1, 4].

1. Initialize the dp array with dimensions (4) x (5), since len(nums1) = 3 (we add 1 for the base case) and len(nums2) = 4 (again, we add 1 for the base case), and fill it with zeros.

1    dp matrix:
2       0  0  0  0  0
3       0  0  0  0  0 
4       0  0  0  0  0 
5       0  0  0  0  0

2. Begin iterating through the dp array starting with i = 1 (for nums1) and j = 1 (for nums2).

3. For i = 1 and j = 1, compare nums1[0] (which is 2) and nums2[0] (which is 5). They are not equal, so we set dp[1][1] to max(dp[0][1], dp[1][0]) which is 0.

1    dp matrix:
2       0  0  0  0  0
3       0  0  0  0  0 
4       0  0  0  0  0 
5       0  0  0  0  0

4. Continue this for the combination of the indices, when you reach i = 1 and j = 2, nums1[0] is 2 and nums2[1] is 2. They match, so we set dp[1][2] to dp[0][1] + 1 which is 1.

1    dp matrix:
2       0  0  0  0  0
3       0  0  1  0  0 
4       0  0  0  0  0 
5       0  0  0  0  0

5. As we proceed, we come to a case where i = 2 and j = 1, nums1[1] is 5 and nums2[0] is 5. They do match, so dp[2][1] = dp[1][0] + 1, hence the value is 1.

1    dp matrix:
2       0  0  0  0  0
3       0  0  1  0  0 
4       0  1  0  0  0 
5       0  0  0  0  0

6. Continue filling the matrix using the rules described above. Finally, the dp matrix looks like:

1    dp matrix:
2       0  0  0  0  0
3       0  0  1  1  1 
4       0  1  1  1  1 
5       0  1  1  2  2

7. The bottom-right value dp[3][4] is 2, indicating the maximum number of "uncrossed lines" we can draw between nums1 and nums2 is 2. These lines connect the pairs (2, 2) and (1, 1) from nums1 and nums2, respectively.

By following these steps, the dynamic programming algorithm efficiently computes the maximum number of uncrossed lines that can be drawn between the two arrays.

Solution Implementation

Time and Space Complexity

The given code implements a dynamic programming solution to find the maximum number of uncrossed lines which can be drawn between two arrays. Here's the analysis of its complexities:

• Time complexity: The code has two nested loops, each iterating over the elements of nums1 (of size m) and nums2 (of size n), respectively. Therefore, the time complexity is O(m * n), since every cell in the DP table dp of size m+1 by n+1 is filled exactly once.

• Space complexity: The space complexity is determined by the size of the table dp, which has (m + 1) * (n + 1) cells. Hence, the space complexity is O(m * n) as we are using an auxiliary 2D array to store the solutions to subproblems.

Learn more about how to find time and space complexity quickly using problem constraints.