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.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

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
  1. Begin iterating through the dp array starting with i = 1 (for nums1) and j = 1 (for nums2).

  2. 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
  1. 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
  1. 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
  1. 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
  1. 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

1class Solution:
2    def max_uncrossed_lines(self, nums1: List[int], nums2: List[int]) -> int:
3        # Get the lengths of the two input lists
4        len_nums1, len_nums2 = len(nums1), len(nums2)
5
6        # Create a 2D array with dimensions (len_nums1+1) x (len_nums2+1)
7        # Initially, fill it with zeros
8        dp = [[0] * (len_nums2 + 1) for _ in range(len_nums1 + 1)]
9
10        # Iterate through each element in nums1
11        for i in range(1, len_nums1 + 1):
12            # Iterate through each element in nums2
13            for j in range(1, len_nums2 + 1):
14                # If the elements in nums1 and nums2 are equal
15                if nums1[i - 1] == nums2[j - 1]:
16                    # Take the value from the diagonal and add 1
17                    dp[i][j] = dp[i - 1][j - 1] + 1
18                else:
19                    # Otherwise, take the max value from either
20                    # the left or the top cell
21                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
22
23        # Return the value in the bottom-right corner of the matrix
24        # which holds the count of the maximum number of uncrossed lines
25        return dp[len_nums1][len_nums2]
26
1class Solution {
2    public int maxUncrossedLines(int[] A, int[] B) {
3        // Lengths of the input arrays.
4        int lengthA = A.length;
5        int lengthB = B.length;
6
7        // Create a 2D array for dynamic programming.
8        int[][] dpArray = new int[lengthA + 1][lengthB + 1];
9
10        // Iterate through each element in both arrays.
11        for (int indexA = 1; indexA <= lengthA; indexA++) {
12            for (int indexB = 1; indexB <= lengthB; indexB++) {
13                // If the current elements in both arrays match,
14                // take the value from the previous indices in both arrays and add one.
15                if (A[indexA - 1] == B[indexB - 1]) {
16                    dpArray[indexA][indexB] = dpArray[indexA - 1][indexB - 1] + 1;
17                } else {
18                    // If they do not match, take the maximum value from the two possibilities:
19                    // (1) one index back in the first array (indexA - 1),
20                    // (2) one index back in the second array (indexB - 1).
21                    dpArray[indexA][indexB] = Math.max(dpArray[indexA - 1][indexB], dpArray[indexA][indexB - 1]);
22                }
23            }
24        }
25
26        // The bottom-right value in the dpArray will have the count of maximum uncrossed lines.
27        return dpArray[lengthA][lengthB];
28    }
29}
30
1class Solution {
2public:
3    int maxUncrossedLines(vector<int>& A, vector<int>& B) {
4        // Find the size of both input vectors
5        int sizeA = A.size(), sizeB = B.size();
6      
7        // Initialize a 2D vector dp to hold the max uncrossed lines count for subproblems
8        vector<vector<int>> dp(sizeA + 1, vector<int>(sizeB + 1));
9      
10        // Iterate over each element in vector A (1-indexed for dp purposes)
11        for (int i = 1; i <= sizeA; ++i) {
12            // Iterate over each element in vector B (1-indexed for dp purposes)
13            for (int j = 1; j <= sizeB; ++j) {
14                // If the current elements in A and B are equal
15                if (A[i - 1] == B[j - 1]) {
16                    // The number of uncrossed lines is 1 plus the number for the previous elements
17                    dp[i][j] = dp[i - 1][j - 1] + 1;
18                } else {
19                    // Otherwise, take the maximum from either excluding current element in A or B
20                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
21                }
22            }
23        }
24      
25        // Return the max uncrossed lines for the whole sequences
26        return dp[sizeA][sizeB];
27    }
28};
29
1function maxUncrossedLines(nums1: number[], nums2: number[]): number {
2    // Get the lengths of both input arrays
3    const lengthNums1 = nums1.length;
4    const lengthNums2 = nums2.length;
5    // Initialize a 2D array for dynamic programming with all values set to 0
6    const dp: number[][] = Array.from({ length: lengthNums1 + 1 }, () => new Array(lengthNums2 + 1).fill(0));
7  
8    // Iterate over both arrays starting from index 1 since dp array is 1-indexed
9    for (let i = 1; i <= lengthNums1; ++i) {
10        for (let j = 1; j <= lengthNums2; ++j) {
11            // For each cell, set the value to the maximum of the cell to the left and the cell above
12            dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
13            // If the current elements in nums1 and nums2 match, set dp[i][j] to the value of 
14            // the diagonal cell dp[i - 1][j - 1] plus 1 (representing this matching pair)
15            if (nums1[i - 1] === nums2[j - 1]) {
16                dp[i][j] = dp[i - 1][j - 1] + 1;
17            }
18        }
19    }
20  
21    // Return the bottom-right cell of the dp array, which represents the maximum number
22    // of uncrossed lines (matches) between nums1 and nums2
23    return dp[lengthNums1][lengthNums2];
24}
25

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.


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27
1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30
1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

Recommended Readings

Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.