Uncrossed Lines (= LCS on Integers)

🎯

Uncrossed Lines (= LCS on Integers)

mediumDPAmazonGoogleFacebook

Imagine you have two sequences of numbers representing points on two parallel lines. You want to connect matching numbers with lines that do not cross each other, maximizing the number of such connections.

💡 This problem is a variation of the classic Longest Common Subsequence (LCS) problem but applied to integer arrays instead of strings. Beginners often struggle because the problem's visual nature (lines not crossing) can be confusing, but it essentially boils down to finding the longest sequence common to both arrays in order.

📋

Problem Statement

Given two integer arrays nums1 and nums2, return the maximum number of connecting lines you can draw between matching numbers in nums1 and nums2 such that no two connecting lines cross. A connecting line connects nums1[i] and nums2[j] if nums1[i] == nums2[j]. Lines cannot intersect.

1 ≤ nums1.length, nums2.length ≤ 5001 ≤ nums1[i], nums2[j] ≤ 2000

💡

Example

Input"nums1 = [1,4,2], nums2 = [1,2,4]"

Output2

We can connect nums1[0] to nums2[0] (both 1) and nums1[2] to nums2[1] (both 2). Connecting 4s would cross lines.

• nums1 and nums2 have no common elements → output 0
• nums1 and nums2 are identical → output is length of nums1
• nums1 or nums2 contains repeated elements → output accounts for multiple matches
• nums1 or nums2 has length 1 → output is 1 if element exists in other array, else 0

🔁

Why DP?

Why greedy fails:

A greedy approach might try to connect the first matching pair and then skip others, but this can lead to suboptimal solutions. For example, nums1=[1,4,2], nums2=[1,2,4]: greedily connecting 1 and 4 first leads to crossing lines or fewer connections.

DP state:

dp[i][j] represents the maximum number of uncrossed lines that can be drawn between the first i elements of nums1 and the first j elements of nums2.

Recurrence:dp[i][j] = dp[i-1][j-1] + 1 if nums1[i-1] == nums2[j-1] else max(dp[i-1][j], dp[i][j-1])

If the current elements match, add 1 to the solution excluding these elements; otherwise, take the best solution excluding one element from either array.

⚠️

Common Mistakes

Forgetting to handle base cases in recursion or DP

Index out of range errors or incorrect results

✅ Explicitly check for indices reaching array lengths and initialize dp with zeros

Mixing up indices when accessing nums1 and nums2 in dp table

Wrong matches leading to incorrect dp values

✅ Use consistent 1-based indexing for dp and 0-based for arrays, adjusting indices accordingly

Not iterating backwards in space optimized DP

Overwrites dp[j-1] before it is used, causing incorrect results

✅ Iterate j from n down to 1 to preserve previous values

Using greedy approach to connect lines as soon as a match is found

Suboptimal number of lines connected due to crossing lines

✅ Use DP to consider all possibilities and avoid crossing

🧠

Brute Force (Pure Recursion)

💡 This approach lays the foundation by exploring all possible ways to connect lines without optimization. It helps understand the problem's structure but is inefficient for large inputs.

Intuition

Try every pair of indices in nums1 and nums2. If elements match, connect them and recurse on the remaining parts. Otherwise, skip one element from either array and recurse.

Algorithm

1. Start from the beginning of both arrays.
2. If elements match, connect and recurse on next indices.
3. If not, recurse by skipping one element from either array.
4. Return the maximum connections found.

💡 The recursion tree grows exponentially because it explores all combinations, making it hard to follow without memoization.

Recurrence:f(i,j) = 1 + f(i+1,j+1) if nums1[i] == nums2[j] else max(f(i+1,j), f(i,j+1))

</>

Code

def max_uncrossed_lines(nums1, nums2):
    def dfs(i, j):
        if i == len(nums1) or j == len(nums2):
            return 0
        if nums1[i] == nums2[j]:
            return 1 + dfs(i+1, j+1)
        else:
            return max(dfs(i+1, j), dfs(i, j+1))
    return dfs(0, 0)

# Example usage
if __name__ == '__main__':
    print(max_uncrossed_lines([1,4,2], [1,2,4]))  # Output: 2

Line Notes

def dfs(i, j):Defines the recursive helper function with current indices

if i == len(nums1) or j == len(nums2):Base case: reached end of either array

if nums1[i] == nums2[j]:Check if current elements match to connect

return max(dfs(i+1, j), dfs(i, j+1))Explore skipping one element from either array

public class Solution {
    public int maxUncrossedLines(int[] nums1, int[] nums2) {
        return dfs(nums1, nums2, 0, 0);
    }
    private int dfs(int[] nums1, int[] nums2, int i, int j) {
        if (i == nums1.length || j == nums2.length) return 0;
        if (nums1[i] == nums2[j]) {
            return 1 + dfs(nums1, nums2, i + 1, j + 1);
        } else {
            return Math.max(dfs(nums1, nums2, i + 1, j), dfs(nums1, nums2, i, j + 1));
        }
    }
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.maxUncrossedLines(new int[]{1,4,2}, new int[]{1,2,4})); // 2
    }
}

Line Notes

public int maxUncrossedLines(int[] nums1, int[] nums2)Entry point calling recursive helper

if (i == nums1.length || j == nums2.length)Base case when either array is fully traversed

if (nums1[i] == nums2[j])Check for matching elements to connect

return Math.max(...)Explore skipping elements from either array

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    int dfs(const vector<int>& nums1, const vector<int>& nums2, int i, int j) {
        if (i == nums1.size() || j == nums2.size()) return 0;
        if (nums1[i] == nums2[j])
            return 1 + dfs(nums1, nums2, i + 1, j + 1);
        else
            return max(dfs(nums1, nums2, i + 1, j), dfs(nums1, nums2, i, j + 1));
    }
    int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
        return dfs(nums1, nums2, 0, 0);
    }
};

int main() {
    Solution sol;
    vector<int> nums1 = {1,4,2};
    vector<int> nums2 = {1,2,4};
    cout << sol.maxUncrossedLines(nums1, nums2) << endl; // 2
    return 0;
}

Line Notes

int dfs(const vector<int>& nums1, const vector<int>& nums2, int i, int j)Recursive helper with current indices

if (i == nums1.size() || j == nums2.size())Base case: end of either array reached

if (nums1[i] == nums2[j])Check for matching elements to connect

return max(...)Try skipping elements from either array

function maxUncrossedLines(nums1, nums2) {
    function dfs(i, j) {
        if (i === nums1.length || j === nums2.length) return 0;
        if (nums1[i] === nums2[j]) {
            return 1 + dfs(i + 1, j + 1);
        } else {
            return Math.max(dfs(i + 1, j), dfs(i, j + 1));
        }
    }
    return dfs(0, 0);
}

// Example usage
console.log(maxUncrossedLines([1,4,2], [1,2,4])); // 2

Line Notes

function dfs(i, j)Defines recursive helper with indices

if (i === nums1.length || j === nums2.length)Base case when end of array reached

if (nums1[i] === nums2[j])Check if elements match to connect

return Math.max(...)Explore skipping elements from either array

⏱

Complexity

TimeO(2^(m+n))

SpaceO(m+n) due to recursion stack

Each call branches into two calls unless elements match, leading to exponential growth.

💡 For arrays of length 20, this approach could make over a million calls, which is impractical.

Interview Verdict: TLE

This approach is too slow for large inputs but is essential to understand the problem's recursive structure.

🧠

Top-Down DP with Memoization

💡 Memoization caches results of subproblems to avoid recomputation, drastically improving efficiency while retaining the recursive structure.

Intuition

Use recursion as before but store results of dp[i][j] so repeated calls return cached results instead of recomputing.

Algorithm

1. Initialize a 2D cache to store results for each pair (i, j).
2. Recursively compute results, checking cache before recursion.
3. If elements match, add 1 plus result of next indices.
4. Otherwise, take max of skipping one element from either array.

💡 Memoization transforms exponential recursion into polynomial time by pruning duplicate computations.

Recurrence:dp[i][j] = 1 + dp[i+1][j+1] if nums1[i] == nums2[j] else max(dp[i+1][j], dp[i][j+1])

</>

Code

def max_uncrossed_lines(nums1, nums2):
    from functools import lru_cache
    @lru_cache(None)
    def dfs(i, j):
        if i == len(nums1) or j == len(nums2):
            return 0
        if nums1[i] == nums2[j]:
            return 1 + dfs(i+1, j+1)
        else:
            return max(dfs(i+1, j), dfs(i, j+1))
    return dfs(0, 0)

# Example usage
if __name__ == '__main__':
    print(max_uncrossed_lines([1,4,2], [1,2,4]))  # Output: 2

Line Notes

from functools import lru_cacheImports memoization decorator to cache function results

@lru_cache(None)Caches dfs results for each (i, j) to avoid recomputation

if i == len(nums1) or j == len(nums2)Base case to stop recursion

return max(dfs(i+1, j), dfs(i, j+1))Explore skipping elements with cached results

import java.util.*;
public class Solution {
    private int[][] memo;
    public int maxUncrossedLines(int[] nums1, int[] nums2) {
        memo = new int[nums1.length][nums2.length];
        for (int[] row : memo) Arrays.fill(row, -1);
        return dfs(nums1, nums2, 0, 0);
    }
    private int dfs(int[] nums1, int[] nums2, int i, int j) {
        if (i == nums1.length || j == nums2.length) return 0;
        if (memo[i][j] != -1) return memo[i][j];
        if (nums1[i] == nums2[j]) {
            memo[i][j] = 1 + dfs(nums1, nums2, i + 1, j + 1);
        } else {
            memo[i][j] = Math.max(dfs(nums1, nums2, i + 1, j), dfs(nums1, nums2, i, j + 1));
        }
        return memo[i][j];
    }
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.maxUncrossedLines(new int[]{1,4,2}, new int[]{1,2,4})); // 2
    }
}

Line Notes

private int[][] memo;2D array to cache results for subproblems

for (int[] row : memo) Arrays.fill(row, -1);Initialize memo with -1 to indicate uncomputed states

if (memo[i][j] != -1) return memo[i][j];Return cached result if available

memo[i][j] = Math.max(...)Store computed result to avoid recomputation

#include <iostream>
#include <vector>
using namespace std;

class Solution {
    vector<vector<int>> memo;
public:
    int dfs(const vector<int>& nums1, const vector<int>& nums2, int i, int j) {
        if (i == nums1.size() || j == nums2.size()) return 0;
        if (memo[i][j] != -1) return memo[i][j];
        if (nums1[i] == nums2[j])
            memo[i][j] = 1 + dfs(nums1, nums2, i + 1, j + 1);
        else
            memo[i][j] = max(dfs(nums1, nums2, i + 1, j), dfs(nums1, nums2, i, j + 1));
        return memo[i][j];
    }
    int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
        memo.assign(nums1.size(), vector<int>(nums2.size(), -1));
        return dfs(nums1, nums2, 0, 0);
    }
};

int main() {
    Solution sol;
    vector<int> nums1 = {1,4,2};
    vector<int> nums2 = {1,2,4};
    cout << sol.maxUncrossedLines(nums1, nums2) << endl; // 2
    return 0;
}

Line Notes

vector<vector<int>> memo;2D vector to store computed results

memo.assign(..., -1);Initialize memo with -1 to mark unvisited states

if (memo[i][j] != -1) return memo[i][j];Return cached result if available

memo[i][j] = max(...)Store computed result to avoid recomputation

function maxUncrossedLines(nums1, nums2) {
    const memo = Array(nums1.length).fill(null).map(() => Array(nums2.length).fill(-1));
    function dfs(i, j) {
        if (i === nums1.length || j === nums2.length) return 0;
        if (memo[i][j] !== -1) return memo[i][j];
        if (nums1[i] === nums2[j]) {
            memo[i][j] = 1 + dfs(i + 1, j + 1);
        } else {
            memo[i][j] = Math.max(dfs(i + 1, j), dfs(i, j + 1));
        }
        return memo[i][j];
    }
    return dfs(0, 0);
}

console.log(maxUncrossedLines([1,4,2], [1,2,4])); // 2

Line Notes

const memo = Array(...).fill(-1);Initialize 2D memo array with -1 for unvisited states

if (memo[i][j] !== -1) return memo[i][j];Return cached result if available

memo[i][j] = Math.max(...)Store computed result to avoid recomputation

return dfs(0, 0);Start recursion from beginning of both arrays

⏱

Complexity

TimeO(m*n)

SpaceO(m*n) for memoization cache and recursion stack

Each subproblem (i,j) is computed once and stored, reducing exponential calls to polynomial.

💡 For arrays of length 500, this means at most 250,000 subproblems, which is efficient.

Interview Verdict: Accepted

This approach is efficient enough for typical constraints and is a common interview solution.

🧠

Bottom-Up DP (Tabulation)

💡 This approach builds the solution iteratively from smaller subproblems, avoiding recursion and making the process explicit and often easier to debug.

Intuition

Create a 2D dp table where dp[i][j] stores the max uncrossed lines for prefixes nums1[:i] and nums2[:j]. Fill the table row by row using the recurrence.

Algorithm

1. Initialize a 2D dp array with zeros for base cases.
2. Iterate through nums1 and nums2 indices.
3. If elements match, dp[i][j] = dp[i-1][j-1] + 1.
4. Else, dp[i][j] = max(dp[i-1][j], dp[i][j-1]).
5. Return dp[m][n] as the final answer.

💡 This method explicitly shows how solutions to smaller prefixes combine to solve larger prefixes.

Recurrence:dp[i][j] = dp[i-1][j-1] + 1 if nums1[i-1] == nums2[j-1] else max(dp[i-1][j], dp[i][j-1])

</>

Code

def max_uncrossed_lines(nums1, nums2):
    m, n = len(nums1), len(nums2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 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[m][n]

# Example usage
if __name__ == '__main__':
    print(max_uncrossed_lines([1,4,2], [1,2,4]))  # Output: 2

Line Notes

dp = [[0] * (n + 1) for _ in range(m + 1)]Initialize dp table with zeros for base cases

for i in range(1, m + 1):Iterate over nums1 indices starting from 1 for 1-based dp indexing

if nums1[i - 1] == nums2[j - 1]:Check if current elements match to extend sequence

dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])If no match, take best excluding one element

public class Solution {
    public int maxUncrossedLines(int[] nums1, int[] nums2) {
        int m = nums1.length, n = nums2.length;
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; 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[m][n];
    }
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.maxUncrossedLines(new int[]{1,4,2}, new int[]{1,2,4})); // 2
    }
}

Line Notes

int[][] dp = new int[m + 1][n + 1];Create dp table with extra row and column for base cases

for (int i = 1; i <= m; i++)Iterate over nums1 indices with 1-based indexing

if (nums1[i - 1] == nums2[j - 1])Check for matching elements to extend sequence

dp[i][j] = Math.max(...)Choose best excluding one element if no match

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size(), n = nums2.size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++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[m][n];
    }
};

int main() {
    Solution sol;
    vector<int> nums1 = {1,4,2};
    vector<int> nums2 = {1,2,4};
    cout << sol.maxUncrossedLines(nums1, nums2) << endl; // 2
    return 0;
}

Line Notes

vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));Initialize dp table with zeros for base cases

for (int i = 1; i <= m; ++i)Iterate over nums1 indices with 1-based indexing

if (nums1[i - 1] == nums2[j - 1])Check for matching elements to extend sequence

dp[i][j] = max(...)Choose best excluding one element if no match

function maxUncrossedLines(nums1, nums2) {
    const m = nums1.length, n = nums2.length;
    const dp = Array(m + 1).fill(null).map(() => Array(n + 1).fill(0));
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; 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[m][n];
}

console.log(maxUncrossedLines([1,4,2], [1,2,4])); // 2

Line Notes

const dp = Array(m + 1).fill(null).map(() => Array(n + 1).fill(0));Initialize 2D dp array with zeros for base cases

for (let i = 1; i <= m; i++)Iterate over nums1 indices with 1-based indexing

if (nums1[i - 1] === nums2[j - 1])Check for matching elements to extend sequence

dp[i][j] = Math.max(...)Choose best excluding one element if no match

⏱

Complexity

TimeO(m*n)

SpaceO(m*n)

We fill an m+1 by n+1 table once, each cell computed in O(1).

💡 For arrays of length 500, this means 250,000 operations, which is efficient and practical.

Interview Verdict: Accepted

This is the standard DP solution for this problem and is optimal in time.

🧠

Space Optimized Bottom-Up DP

💡 Since dp[i][j] depends only on dp[i-1][j-1], dp[i-1][j], and dp[i][j-1], we can optimize space by using a single 1D array updated in reverse order.

Intuition

Use a 1D dp array representing the previous row and update it for the current row, iterating backwards to preserve needed values.

Algorithm

1. Initialize a 1D dp array of length n+1 with zeros.
2. Iterate over nums1 elements (rows).
3. For each nums1[i], iterate nums2 elements (columns) backwards.
4. If elements match, update dp[j] = prev + 1 where prev stores dp[j-1] from previous iteration.
5. Else, dp[j] = max(dp[j], dp[j-1]).

💡 Backward iteration ensures dp[j-1] from previous iteration is not overwritten before use.

Recurrence:dp[j] = dp[j-1] + 1 if nums1[i-1] == nums2[j-1] else max(dp[j], dp[j-1])

</>

Code

def max_uncrossed_lines(nums1, nums2):
    m, n = len(nums1), len(nums2)
    dp = [0] * (n + 1)
    for i in range(1, m + 1):
        prev = 0
        for j in range(1, n + 1):
            temp = dp[j]
            if nums1[i - 1] == nums2[j - 1]:
                dp[j] = prev + 1
            else:
                dp[j] = max(dp[j], dp[j - 1])
            prev = temp
    return dp[n]

# Example usage
if __name__ == '__main__':
    print(max_uncrossed_lines([1,4,2], [1,2,4]))  # Output: 2

Line Notes

dp = [0] * (n + 1)Initialize 1D dp array for previous row results

prev = 0Stores dp[j-1] from previous iteration to use in current update

temp = dp[j]Temporarily store current dp[j] before updating

dp[j] = prev + 1Update dp[j] when elements match using previous diagonal value

public class Solution {
    public int maxUncrossedLines(int[] nums1, int[] nums2) {
        int m = nums1.length, n = nums2.length;
        int[] dp = new int[n + 1];
        for (int i = 1; i <= m; i++) {
            int prev = 0;
            for (int j = 1; j <= n; j++) {
                int temp = dp[j];
                if (nums1[i - 1] == nums2[j - 1]) {
                    dp[j] = prev + 1;
                } else {
                    dp[j] = Math.max(dp[j], dp[j - 1]);
                }
                prev = temp;
            }
        }
        return dp[n];
    }
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.maxUncrossedLines(new int[]{1,4,2}, new int[]{1,2,4})); // 2
    }
}

Line Notes

int[] dp = new int[n + 1];1D dp array to store previous row results

int prev = 0;Stores dp[j-1] from previous iteration for diagonal reference

int temp = dp[j];Temporarily save current dp[j] before update

dp[j] = prev + 1;Update dp[j] when elements match using previous diagonal value

#include <iostream>
#include <vector>
using namespace std;

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

int main() {
    Solution sol;
    vector<int> nums1 = {1,4,2};
    vector<int> nums2 = {1,2,4};
    cout << sol.maxUncrossedLines(nums1, nums2) << endl; // 2
    return 0;
}

Line Notes

vector<int> dp(n + 1, 0);1D dp vector for previous row results

int prev = 0;Stores dp[j-1] from previous iteration for diagonal reference

int temp = dp[j];Temporarily save current dp[j] before update

dp[j] = prev + 1;Update dp[j] when elements match using previous diagonal value

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

console.log(maxUncrossedLines([1,4,2], [1,2,4])); // 2

Line Notes

const dp = new Array(n + 1).fill(0);Initialize 1D dp array for previous row results

let prev = 0;Stores dp[j-1] from previous iteration for diagonal reference

let temp = dp[j];Temporarily save current dp[j] before update

dp[j] = prev + 1;Update dp[j] when elements match using previous diagonal value

⏱

Complexity

TimeO(m*n)

SpaceO(n)

We use a single dp array of size n+1 and update it for each row, reducing space from O(m*n) to O(n).

💡 For arrays of length 500, this reduces memory usage significantly while maintaining speed.

Interview Verdict: Accepted

This is the most space-efficient DP solution commonly accepted in interviews.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, coding the bottom-up DP or space optimized DP is usually best for clarity and efficiency.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(2^(m+n))	O(m+n) recursion stack	Yes (deep recursion)	Yes, but inefficient	Mention only - never code
2. Top-Down DP with Memoization	O(m*n)	O(m*n) memo + recursion stack	Possible but unlikely for constraints	Yes, via memo table	Good for quick optimization of brute force
3. Bottom-Up DP (Tabulation)	O(m*n)	O(m*n)	No	Yes, via dp table	Standard solution to code
4. Space Optimized Bottom-Up DP	O(m*n)	O(n)	No	Harder, requires extra bookkeeping	Mention if asked about optimization

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding each approach, and prepare to explain tradeoffs clearly in interviews.

How to Present

Clarify the problem and constraints.Explain the brute force recursive approach to show understanding.Introduce memoization to optimize recursion.Present bottom-up DP for clarity and efficiency.Discuss space optimization if time permits.

Time Allocation

Clarify: 3min → Approach: 5min → Code: 10min → Test: 5min. Total ~23min

What the Interviewer Tests

Understanding of DP concepts, ability to optimize naive solutions, and clarity in explaining tradeoffs.

Common Follow-ups

• What if arrays are very large? → Use space optimized DP.
• Can you reconstruct the actual lines drawn? → Use DP table to backtrack.

💡 These follow-ups test deeper understanding of DP optimization and solution reconstruction.

🔍

Pattern Recognition

When to Use

1) Problem involves two sequences; 2) Need to find maximum matching subsequence; 3) Order matters; 4) No crossing or overlapping allowed.

Signature Phrases

maximum number of connecting linesno two connecting lines crossmatching elements in order

NOT This Pattern When

Problems involving subsequence sums or partitions without order constraints are different.

Similar Problems

Longest Common Subsequence - classic string versionMaximum Length of Repeated Subarray - similar but requires contiguous matches

Practice

1. Consider the following Python code that counts palindromic substrings using the expand around center approach. What is the final returned count when the input string is "aaa"?

def countSubstrings(s: str) -> int:
    n = len(s)
    count = 0

    def expand(left, right):
        nonlocal count
        while left >= 0 and right < n and s[left] == s[right]:
            count += 1
            left -= 1
            right += 1

    for i in range(n):
        expand(i, i)      # Odd length palindromes
        expand(i, i + 1)  # Even length palindromes

    return count

print(countSubstrings('aaa'))  # ?

easy

A. 3

B. 6

C. 4

D. 5

Solution

1. Step 1: Trace expansions for i=0

   expand(0,0) counts 'a' -> count=1; expand(0,1) counts 'aa' -> count=2

2. Step 2: Trace expansions for i=1 and i=2

   i=1: expand(1,1) counts 'a', 'aaa' -> +2; expand(1,2) counts 'aa' -> +1; i=2: expand(2,2) counts 'a' -> +1; total count=6

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   All palindromic substrings: 'a', 'a', 'a', 'aa', 'aa', 'aaa' [OK]

Hint: Count includes all odd and even length palindromes [OK]

Common Mistakes:

• Counting only single characters or missing even length palindromes

2. The following code attempts to implement the space-optimized DP for longest common substring. Identify the line containing the subtle bug that causes incorrect results on some inputs.

def longest_common_substring_space_optimized_buggy(s1, s2):
    n, m = len(s1), len(s2)
    dp = [0] * (m + 1)
    max_len = 0
    for i in range(1, n + 1):
        for j in range(1, m + 1):  # Note: iterating forward
            if s1[i - 1] == s2[j - 1]:
                dp[j] = dp[j - 1] + 1
                if dp[j] > max_len:
                    max_len = dp[j]
            else:
                dp[j] = 0
    return max_len

medium

A. Line with 'dp[j] = dp[j - 1] + 1' updating dp

B. Line with 'dp = [0] * (m + 1)' initializing dp array

C. Line with 'if dp[j] > max_len:' updating max_len

D. Line with 'for j in range(1, m + 1):' iterating forward

Solution

1. Step 1: Understand dp array update dependency

   dp[j] depends on dp[j-1] from previous iteration of inner loop, so iterating forward overwrites dp[j-1] before use.

2. Step 2: Identify iteration order bug

   Iterating j forward causes dp[j-1] to be updated before dp[j], corrupting the chain of matching lengths.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Changing inner loop to iterate backward fixes the bug [OK]

Hint: DP update depends on previous dp[j-1], so iterate backward [OK]

Common Mistakes:

• Updating dp forward overwrites needed values
• Incorrect max_len update timing
• Wrong dp initialization size

3. What is the time complexity of the space-optimized bottom-up DP solution for wildcard matching where m and n are the lengths of the input string and pattern respectively?

medium

A. O(m + n)

B. O(m * n)

C. O(2^(m + n))

D. O(m * n^2)

Solution

1. Step 1: Identify loops in the DP code

   The code has nested loops: outer loop runs m times, inner loop runs n times.

2. Step 2: Calculate total operations

   Each iteration does O(1) work, so total time is O(m * n).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   DP fills a table of size m by n once [OK]

Hint: Nested loops over string and pattern lengths imply O(m*n) [OK]

Common Mistakes:

• Confusing with brute force exponential
• Assuming linear time
• Forgetting nested loops

4. What is the time complexity of the bottom-up DP solution for Word Break II that uses nested loops over the string and dictionary words, and concatenates sentences stored in dp arrays?

medium

A. O(n^3) due to nested loops and string concatenations

B. O(n^2 * m) because each substring is checked against dictionary words

C. O(2^n) because all segmentations are explored

D. O(n * m) where n = length of string, m = number of words in dictionary

Solution

1. Step 1: Identify nested loops and operations

   Outer loop runs n times, inner loop over dictionary words m times, and for each match, concatenation of strings from dp arrays occurs.

2. Step 2: Analyze concatenation cost

   Concatenation and copying sentences can cost up to O(n) each, and there can be O(n^2) substrings, leading to O(n^3) total time.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Nested loops plus string concatenations cause cubic time [OK]

Hint: String concatenation inside nested loops causes O(n^3) [OK]

Common Mistakes:

• Confusing exponential brute force with DP complexity
• Ignoring concatenation cost

5. Suppose the problem is modified so that characters can be deleted multiple times (i.e., you can reuse characters from s1 and s2 any number of times) to minimize the ASCII delete sum to make the strings equal. Which of the following approaches correctly adapts the solution?

hard

A. Use the same DP but allow transitions to reuse characters by not advancing indices when characters match

B. Use a greedy approach deleting characters with the highest ASCII values first until strings match

C. Apply the original DP without changes since reuse does not affect the minimum delete sum

D. Modify the DP to consider infinite reuse by converting it into an unbounded knapsack style problem with nested loops over characters

Solution

1. Step 1: Understand reuse changes problem nature

   Allowing reuse means characters can be matched multiple times, similar to unbounded knapsack.

2. Step 2: Adapt DP accordingly

   DP must allow multiple uses of characters, requiring nested loops to consider all reuse possibilities, unlike original one-to-one matching.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Unbounded knapsack analogy fits reuse scenario [OK]

Hint: Reuse means unbounded knapsack style DP needed [OK]

Common Mistakes:

• Assuming original DP works unchanged with reuse