Uncrossed Lines

Medium
581.

Uncrossed Lines

Uncrossed Lines is a medium coding problem on arrays and dynamic programming, asked in Amazon and Google interviews.

Write nums1 on one line and nums2 on another. You may draw a connecting line between nums1[i] and nums2[j] when nums1[i] == nums2[j], provided no two lines cross and each number is used at most once.

Return the maximum number of connecting lines.

Example 1

Input
nums1 = [1,4,2], nums2 = [1,2,4]
Output
2
Explanation
Connect the 1s and then either the 4s or the 2s — connecting both would cross.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var maxUncrossedLines = function(nums1, nums2) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Uncrossed Lines — Solution in Python, Java & C++

Uncrossed Lines solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Uncrossed Lines is a medium coding problem on arrays and dynamic programming, asked in Amazon and Google interviews.

  • Difficulty: Medium
  • Topics: Arrays, Dynamic Programming
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Write nums1 on one line and nums2 on another. You may draw a connecting line between nums1[i] and nums2[j] when nums1[i] == nums2[j], provided no two lines cross and each number is used at most once.

Return the maximum number of connecting lines.

Example 1

Input: nums1 = [1,4,2], nums2 = [1,2,4]
Output: 2
Explanation: Connect the 1s and then either the 4s or the 2s — connecting both would cross.

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

Hints for Uncrossed Lines

  1. Hint 1

    Non-crossing means the connected indices must increase together on both lines.

  2. Hint 2

    That is precisely a common subsequence.

  3. Hint 3

    So the answer is the length of the longest common subsequence of the two arrays.

How to solve Uncrossed Lines

"No two lines cross" forces the matched index pairs to be increasing in both arrays — which is the definition of a common subsequence. The problem is LCS wearing a different hat.

Approach

  1. Let dp[i][j] be the answer for the prefixes nums1[0..i) and nums2[0..j).
  2. If the last elements match, connect them: dp[i][j] = dp[i-1][j-1] + 1.
  3. Otherwise take the better of dropping one element from either side.
  4. Return dp[n][m].

Why it works

Two lines (i1, j1) and (i2, j2) cross exactly when i1 < i2 but j1 > j2. Forbidding that means the matched pairs form an increasing sequence in both index spaces — a common subsequence, whose maximum length the table computes.

Complexity

  • Time — O(n · m)
  • Space — O(n · m), reducible to O(m)

Pitfalls

  • Greedily connecting the first available equal pair can block a longer non-crossing set.
  • Values may repeat, so counting shared values with a frequency map over-reports.
  • The recurrence is the same as LCS on strings — the elements just happen to be integers.

Reference solution

Python

from typing import List

def maxUncrossedLines(nums1: List[int], nums2: List[int]) -> int:
    n, m = len(nums1), len(nums2)
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if nums1[i - 1] == nums2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[n][m]

Java

public static int maxUncrossedLines(int[] nums1, int[] nums2) {
    int n = nums1.length, m = nums2.length;
    int[][] dp = new int[n + 1][m + 1];
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (nums1[i - 1] == nums2[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
            else dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
        }
    }
    return dp[n][m];
}

C++

int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
    int n = (int) nums1.size(), m = (int) nums2.size();
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (nums1[i - 1] == nums2[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
            else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
        }
    }
    return dp[n][m];
}

JavaScript

var maxUncrossedLines = function(nums1, nums2) {
    const n = nums1.length, m = nums2.length;
    const dp = [];
    for (let i = 0; i <= n; i++) dp.push(new Array(m + 1).fill(0));
    for (let i = 1; i <= n; i++) {
        for (let j = 1; j <= m; j++) {
            if (nums1[i - 1] === nums2[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
            else dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
        }
    }
    return dp[n][m];
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Dynamic Programming