Uncrossed Lines

Uncrossed Lines

What is this problem about?

The Uncrossed Lines interview question is a fascinating visualization of a classic sequence problem. You are given two integer arrays, nums1 and nums2. You draw lines between matching numbers in the two arrays, but there's a catch: the lines cannot intersect. Your goal is to find the maximum number of such non-crossing lines you can draw. This problem is essentially asking for the Longest Common Subsequence (LCS) between the two arrays.

Why is this asked in interviews?

Companies like Microsoft and PhonePe use the Uncrossed Lines coding problem to test a candidate's ability to recognize underlying algorithmic patterns. On the surface, it looks like a geometry or coordinate problem, but it’s actually a classic Dynamic Programming challenge. Identifying this transformation is a key sign of a senior-level problem solver.

Algorithmic pattern used

The primary Array, Dynamic Programming interview pattern used here is the Longest Common Subsequence (LCS). We build a 2D table where dp[i][j] represents the maximum number of uncrossed lines that can be drawn using the first i elements of nums1 and the first j elements of nums2. If nums1[i] == nums2[j], we can draw a line, adding 1 to the result of the previous sub-problem (dp[i-1][j-1]). Otherwise, we take the maximum of skipping an element from either array.

Example explanation

Let nums1 = [1, 4, 2] and nums2 = [1, 2, 4].

1. We can connect the 1s.
2. If we connect the 4s, we can't connect the 2s because the lines would cross.
3. Alternatively, if we connect the 1s and then the 2s, the lines don't cross.
4. The maximum number of non-crossing lines is 2 (connecting the 1s and the 2s, or the 1s and the 4s).

Common mistakes candidates make

The most common mistake is trying to solve this greedily—connecting the first matching pair you see. Greedy approaches fail here because connecting a pair early might block two or more other pairs that could have been connected later. Another mistake is failing to recognize that the "no crossing" rule is mathematically equivalent to preserving the relative order of elements, which is the definition of a subsequence.

Interview preparation tip

Always look for "hidden" problems. If a problem describes a complex physical constraint (like lines crossing), try to translate it into a mathematical or string-based constraint. Mastering the LCS pattern is essential, as it appears in many different guises in technical interviews.