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 diagonaldp[i - 1][j - 1]
and add 1 to it because we have found a match, and add it to the currentdp[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 fromnums1
(use the value indp[i - 1][j]
) or by including one more element fromnums2
(use the value indp[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)
, wherem
is the length ofnums1
andn
is the length ofnums2
. 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 index1
, because the0
-th row and column represent the base case where either of the input sequences is empty. -
For every pair of indices
i
from1
tom
andj
from1
ton
, we check if the elementsnums1[i - 1]
andnums2[j - 1]
match.-
If
nums1[i - 1] == nums2[j - 1]
, this means that we can extend a common subsequence found up todp[i-1][j-1]
. We add1
to the value ofdp[i-1][j-1]
and store it indp[i][j]
. This represents extending the length of the current longest common subsequence by1
.- Mathematically, it is represented as:
1dp[i][j] = dp[i-1][j-1] + 1
- Mathematically, it is represented as:
-
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 betweendp[i-1][j]
anddp[i][j-1]
.-
This means we are either including the
i-th
element fromnums1
and not thej-th
element fromnums2
, 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 ofdp[m][n]
will give us the maximum number of connecting lines we can draw. This represents the length of the longest common subsequence betweennums1
andnums2
.
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 EvaluatorExample Walkthrough
Let's illustrate the solution approach with small example arrays nums1 = [2, 5, 1]
and nums2 = [5, 2, 1, 4]
.
- Initialize the
dp
array with dimensions(4) x (5)
, sincelen(nums1) = 3
(we add 1 for the base case) andlen(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
-
Begin iterating through the
dp
array starting withi = 1
(fornums1
) andj = 1
(fornums2
). -
For
i = 1
andj = 1
, comparenums1[0]
(which is2
) andnums2[0]
(which is5
). They are not equal, so we setdp[1][1]
tomax(dp[0][1], dp[1][0])
which is0
.
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
- Continue this for the combination of the indices, when you reach
i = 1
andj = 2
,nums1[0]
is2
andnums2[1]
is 2. They match, so we setdp[1][2]
todp[0][1] + 1
which is1
.
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
- As we proceed, we come to a case where
i = 2
andj = 1
,nums1[1]
is5
andnums2[0]
is5
. They do match, sodp[2][1] = dp[1][0] + 1
, hence the value is1
.
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
- 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
- The bottom-right value
dp[3][4]
is2
, indicating the maximum number of "uncrossed lines" we can draw betweennums1
andnums2
is2
. These lines connect the pairs(2, 2)
and(1, 1)
fromnums1
andnums2
, 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 sizem
) andnums2
(of sizen
), respectively. Therefore, the time complexity isO(m * n)
, since every cell in the DP tabledp
of sizem+1
byn+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 isO(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.
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
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
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.