Uncrossed Lines (= LCS on Integers)

▶

Steps

setup

Initialize DP array

Create a dp array of length n+1 (4) initialized with zeros, representing the base case where no elements have been matched yet.

💡 Initializing dp with zeros sets the foundation for building up the solution; it represents the LCS length when one of the arrays is empty.

Line:

dp = [0] * (n + 1)

💡 The dp array length is one more than nums2 length to handle base cases easily.

fill_row

Start outer loop: i=1 (nums1[0] = 1)

Begin processing the first element of nums1 (value 1). Reset prev to 0 before inner loop.

💡 Resetting prev is crucial to track dp[j-1] from the previous iteration for correct updates.

Line:

for i in range(1, m + 1):
    prev = 0

💡 prev holds the dp[j-1] value from the previous iteration to compute dp[j] when elements match.

fill_cells

Inner loop j=1: compare nums1[0]=1 and nums2[0]=1

Compare nums1[0] and nums2[0], both are 1, so they match. Update dp[1] = prev + 1 = 0 + 1 = 1.

💡 When elements match, we extend the longest uncrossed lines by 1, using prev which holds dp[j-1] from the previous iteration.

Line:

temp = dp[j]
if nums1[i - 1] == nums2[j - 1]:
    dp[j] = prev + 1
prev = temp

💡 Matching elements increase the LCS length by 1 at this position.

fill_cells

Inner loop j=2: compare nums1[0]=1 and nums2[1]=2

Compare nums1[0] = 1 and nums2[1] = 2, no match. Update dp[2] = max(dp[2], dp[1]) = max(0,1) = 1.

💡 When elements don't match, we carry forward the best LCS length found so far between nums1[0..i-1] and nums2[0..j-1].

Line:

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

💡 Non-matching elements do not increase LCS length; dp carries forward the maximum so far.

fill_cells

Inner loop j=3: compare nums1[0]=1 and nums2[2]=4

Compare nums1[0] = 1 and nums2[2] = 4, no match. Update dp[3] = max(dp[3], dp[2]) = max(0,1) = 1.

💡 Again, no match means we keep the best LCS length so far for this subproblem.

Line:

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

💡 The dp array accumulates the best LCS length as we move through nums2.

fill_row

Start outer loop: i=2 (nums1[1] = 4)

Begin processing the second element of nums1 (value 4). Reset prev to 0 before inner loop.

💡 Resetting prev prepares for the next row of dp updates based on the new nums1 element.

Line:

for i in range(1, m + 1):
    prev = 0

💡 Each outer loop iteration corresponds to processing one element of nums1.

fill_cells

Inner loop j=1: compare nums1[1]=4 and nums2[0]=1

Compare nums1[1] = 4 and nums2[0] = 1, no match. Update dp[1] = max(dp[1], dp[0]) = max(1,0) = 1.

💡 No match means dp[j] keeps the best LCS length so far for this subproblem.

Line:

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

💡 dp array values can stay the same if no better match is found.

fill_cells

Inner loop j=2: compare nums1[1]=4 and nums2[1]=2

Compare nums1[1] = 4 and nums2[1] = 2, no match. Update dp[2] = max(dp[2], dp[1]) = max(1,1) = 1.

💡 No match means dp[j] keeps the best LCS length so far.

Line:

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

💡 dp values propagate forward when no better match is found.

fill_cells

Inner loop j=3: compare nums1[1]=4 and nums2[2]=4

Compare nums1[1] = 4 and nums2[2] = 4, they match. Update dp[3] = prev + 1 = 1 + 1 = 2.

💡 A match increases the LCS length by 1, using prev which holds dp[j-1] from the previous iteration.

Line:

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

💡 Matching elements extend the longest uncrossed lines found so far.

fill_row

Start outer loop: i=3 (nums1[2] = 2)

Begin processing the third element of nums1 (value 2). Reset prev to 0 before inner loop.

💡 Resetting prev prepares for the next row of dp updates based on the new nums1 element.

Line:

for i in range(1, m + 1):
    prev = 0

💡 Each outer loop iteration corresponds to processing one element of nums1.

fill_cells

Inner loop j=1: compare nums1[2]=2 and nums2[0]=1

Compare nums1[2] = 2 and nums2[0] = 1, no match. Update dp[1] = max(dp[1], dp[0]) = max(1,0) = 1.

💡 No match means dp[j] keeps the best LCS length so far.

Line:

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

💡 dp values propagate forward when no better match is found.

fill_cells

Inner loop j=2: compare nums1[2]=2 and nums2[1]=2

Compare nums1[2] = 2 and nums2[1] = 2, they match. Update dp[2] = prev + 1 = 1 + 1 = 2.

💡 A match increases the LCS length by 1, using prev which holds dp[j-1] from the previous iteration.

Line:

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

💡 Matching elements extend the longest uncrossed lines found so far.

fill_cells

Inner loop j=3: compare nums1[2]=2 and nums2[2]=4

Compare nums1[2] = 2 and nums2[2] = 4, no match. Update dp[3] = max(dp[3], dp[2]) = max(2,2) = 2.

💡 No match means dp[j] keeps the best LCS length so far.

Line:

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

💡 dp values propagate forward when no better match is found.

traverse

Algorithm complete: final dp array

All elements processed. The dp array now holds the lengths of the longest uncrossed lines for all prefixes. The answer is dp[n] = dp[3] = 2.

💡 The final dp array summarizes the maximum uncrossed lines found between the full arrays.

Line:

return dp[n]

💡 The last cell in dp contains the length of the longest uncrossed lines.

def max_uncrossed_lines(nums1, nums2):
    m, n = len(nums1), len(nums2)
    dp = [0] * (n + 1)  # STEP 1: Initialize dp array
    for i in range(1, m + 1):  # STEP 2,6,10: Outer loop over nums1
        prev = 0  # Reset prev at start of each row
        for j in range(1, n + 1):  # Inner loop over nums2
            temp = dp[j]  # Store current dp[j] before update
            if nums1[i - 1] == nums2[j - 1]:  # STEP 3,9,12: Check for match
                dp[j] = prev + 1  # Update dp[j] on match
            else:
                dp[j] = max(dp[j], dp[j - 1])  # Update dp[j] on no match
            prev = temp  # Update prev for next iteration
    return dp[n]  # STEP 14: Return final answer

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

📊

Uncrossed Lines (= LCS on Integers) - Watch the Algorithm Execute, Step by Step

Watching each update to the dp array reveals how the algorithm builds solutions to subproblems incrementally, making the logic behind the final answer clear without needing to read code.

Initializing dp array

i\w	0	1	2	3
i=0	0	0	0	0

dp initialized

Item 0 - wt:1 val:0

i\w	0	1	2	3
i=0	0	0	0	0

processing nums1[0]=1

Item 0 - wt:1 val:1

i\w	0	1	2	3
i=0	0	1	0	0

match, dp[1] updated

Item 0 - wt:2 val:1

i\w	0	1	2	3
i=0	0	1	1	0

no match, dp[2] updated

Item 0 - wt:4 val:1

i\w	0	1	2	3
i=0	0	1	1	1

no match, dp[3] updated

Item 1 - wt:4 val:0

i\w	0	1	2	3
i=0	0	1	1	1

processing nums1[1]=4

Item 1 - wt:1 val:1

i\w	0	1	2	3
i=0	0	1	1	1

no match, dp[1] unchanged

Item 1 - wt:2 val:1

i\w	0	1	2	3
i=0	0	1	1	1

no match, dp[2] unchanged

Item 1 - wt:4 val:2

i\w	0	1	2	3
i=0	0	1	1	2

match, dp[3] updated

Item 2 - wt:2 val:0

i\w	0	1	2	3
i=0	0	1	1	2

processing nums1[2]=2

Item 2 - wt:1 val:1

i\w	0	1	2	3
i=0	0	1	1	2

no match, dp[1] unchanged

Item 2 - wt:2 val:2

i\w	0	1	2	3
i=0	0	1	2	2

match, dp[2] updated

Item 2 - wt:4 val:2

i\w	0	1	2	3
i=0	0	1	2	2

no match, dp[3] unchanged

Item 2 - wt:4 val:2

i\w	0	1	2	3
i=0	0	1	2	2

final answer

Key Takeaways

✓ The dp array stores the length of the longest uncrossed lines for prefixes of nums1 and nums2, updated incrementally.

This insight is hard to see from code alone because the 1D dp array reuses space and relies on careful ordering of updates.

✓ Matching elements increase the dp value by 1 using the prev variable, which holds the dp value from the previous iteration's previous column.

Understanding the role of prev clarifies how the algorithm avoids overwriting needed values during iteration.

✓ When elements don't match, dp[j] takes the maximum of dp[j] and dp[j-1], propagating the best LCS length found so far.

This decision ensures the dp array always reflects the optimal solution up to the current indices.

Practice

1. You need to transform one string into another using the minimum number of insertions, deletions, and substitutions. Which algorithmic approach guarantees finding the optimal solution efficiently?

easy

A. Dynamic Programming that builds solutions for all prefixes of both strings

B. Greedy algorithm that replaces characters whenever they differ

C. Divide and conquer by splitting strings at midpoint and solving recursively

D. Backtracking all possible sequences of edits without memoization

Solution

1. Step 1: Understand problem requires minimal edits including insertions, deletions, and substitutions

   These operations depend on overlapping subproblems, making DP suitable.

2. Step 2: Identify approach that solves all subproblems efficiently

   Dynamic Programming computes minimal edits for all prefixes, ensuring optimality and polynomial time complexity.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   DP covers all prefix pairs systematically [OK]

Hint: Optimal edit distance requires DP over all prefix pairs [OK]

Common Mistakes:

• Assuming greedy always works
• Thinking divide and conquer alone suffices
• Ignoring overlapping subproblems

2. You are given three strings s1, s2, and s3. Determine if s3 can be formed by interleaving the characters of s1 and s2 while preserving the order of characters in each string. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Pure brute force recursion without memoization to explore all character combinations

B. Greedy algorithm that picks characters from s1 or s2 whenever they match s3 sequentially

C. Dynamic Programming using a 2D table to track interleaving possibilities for prefixes of s1 and s2

D. Sorting all strings and then comparing if s3 is a merged sorted string of s1 and s2

Solution

1. Step 1: Understand problem constraints

   The problem requires preserving the order of characters from both s1 and s2 to form s3. This rules out greedy and sorting approaches.

2. Step 2: Identify suitable algorithm

   Dynamic Programming with a 2D table tracks whether prefixes of s1 and s2 can form prefixes of s3, guaranteeing an optimal solution.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   DP ensures all prefix combinations are checked systematically [OK]

Hint: Interleaving requires DP to track prefix matches [OK]

Common Mistakes:

• Assuming greedy works because characters match sequentially
• Thinking sorting helps preserve order

3. Consider the following code snippet implementing the bottom-up DP solution for Word Break II. Given s = "catsanddog" and wordDict = ["cat", "cats", "and", "sand", "dog"], what is the value of dp[3] after the outer loop iteration where i = 3 completes?

easy

A. ["and dog"]

B. ["and", "sand"]

C. ["dog"]

D. ["sand dog"]

Solution

1. Step 1: Identify substring starting at index 3

   Substring s[3:] = "sanddog". Check which words in dictionary start at index 3: "sand" matches.

2. Step 2: Build dp[3]

   For word "sand" (length 4), dp[3 + 4] = dp[7] contains ["dog"]. Append "sand" + " " + "dog" -> "sand dog" to dp[3]. No other words match at index 3.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   dp[3] = ["sand dog"] after iteration i=3 [OK]

Hint: Check substring matches and dp lookup carefully [OK]

Common Mistakes:

• Confusing index offsets or missing concatenation spaces

4. What is the time complexity of the space-optimized bottom-up DP solution for regular expression matching with input string length m and pattern length n?

medium

A. O(2^(m + n)) exponential due to backtracking

B. O(m + n) linear in combined length

C. O(m * n) due to nested iteration over string and pattern

D. O(n^2) quadratic in pattern length only

Solution

1. Step 1: Identify loops in the DP solution

   The outer loop iterates over the string length m, and the inner loop iterates over the pattern length n.

2. Step 2: Calculate total operations

   Each iteration of the outer loop runs the inner loop fully, resulting in m * n operations.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   DP table of size m by n is filled once [OK]

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

Common Mistakes:

• Confusing exponential backtracking with DP complexity

5. Suppose the problem is modified so that you want to find the minimum cuts for palindrome partitioning but now the input string can contain wildcard characters '?' that can match any single character. Which of the following approaches correctly adapts the optimal DP solution to handle wildcards?

hard

A. Replace all '?' with all possible characters and run DP multiple times, taking minimum cuts over all results

B. Precompute all palindrome substrings ignoring '?', then run DP as usual

C. Use pure recursion with memoization since DP cannot handle wildcards efficiently

D. Modify palindrome checks to treat '?' as matching any character during center expansions, keeping the same DP structure

Solution

1. Step 1: Understand wildcard impact on palindrome checks

   Wildcards '?' can match any character, so palindrome checks must be adapted to treat '?' as a match with any character.

2. Step 2: Adapt DP palindrome center expansion

   Modify the center expansion condition to allow s[left] == s[right] or either is '?', preserving O(n^2) time and DP structure.

3. Step 3: Evaluate other options

   Precomputing ignoring '?' is incorrect as it misses wildcard matches. Pure recursion is inefficient. Replacing '?' with all characters is exponential and impractical.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Adapting palindrome checks for '?' preserves DP correctness and efficiency [OK]

Hint: Adapt palindrome checks, keep DP structure for wildcards [OK]

Common Mistakes:

• Ignoring wildcard impact on palindrome checks
• Trying exponential brute force over all replacements
• Assuming DP cannot handle wildcards