1035. Uncrossed Lines

Comments

Problem Setting

We write the integers of A and B (in the order they are given) on two separate horizontal lines.

Now, we may draw a straight line connecting two numbers A[i] and B[j] as long as A[i] == B[j], and the line we draw does not intersect any other connecting (non-horizontal) line.

Return the maximum number of connecting lines we can draw in this way.

Link for Problem: leetcode

Example 1:

image

Input: A = [1,4,2], B = [1,2,4]

Output: 2

Explanation: We can draw 2 uncrossed lines as in the diagram. We cannot draw 3 uncrossed lines, because the line from A[1]=4 to B[2]=4 will intersect the line from A[2]=2 to B[1]=2.

Example 2:

Input: A = [2,5,1,2,5], B = [10,5,2,1,5,2]

Output: 3

Example 3:

Input: A = [1,3,7,1,7,5], B = [1,9,2,5,1]

Output: 2

Solution from hanshaohey

In [1]:
class Solution(object):
    def maxUncrossedLines(self, A, B):
        """
        :type A: List[int]
        :type B: List[int]
        :rtype: int
        """
        memo={}
        la,lb=len(A),len(B)
        def helper(i,j):
            if i>=la or j>=lb:
                return 0
            if (i,j) in memo:
                return memo[i,j]
            if A[i]==B[j]:
                ans=1+helper(i+1,j+1)
            else:
                ans=max(helper(i+1,j),helper(i,j+1))
            memo[i,j]=ans
            return ans
        return helper(0,0)

This problem can be solved by "Recursive function" and "Dynamic Programming" approach to re-use the calculated intermediate result for the final result.

In the above example, helper is the recursive function to calculate the intermediate/final results at given conditions (i, j). The memo variable stores those intermediate results

Tips to use a dictionary for dynamic programming

In [5]:
# dictionary can be indexed by 2 dimentions and keys will be tubple
d = {}
d[1, 2] = 1
d[1, 3] = 2
d[3, 1] = 5
d
Out[5]:
{(1, 2): 1, (1, 3): 2, (3, 1): 5}
In [6]:
# dictionary can be indexed by N dimentions and keys will be tubple
d = {}
d[1, 2, 3] = 1
d[1, 3, 5] = 2
d[3, 1, 's'] = 5
d
Out[6]:
{(1, 2, 3): 1, (1, 3, 5): 2, (3, 1, 's'): 5}

Step-by-step understanding

The overall flow is as below:

  1. Initial setup
  2. Define the recursive function helper
  3. Execute helper with (i, j) = (0, 0) as a starting point.

Initial setup

This step defines the variables for storing intermediate results as memo and gets the length of input lists as la and lb

# dictionary to store intermediate results for i, j 
memo={}

# length of the list A and B
la,lb=len(A),len(B)

Define the recursive function helper

What we want to implement for a recursive function are as follows:

Input & Output

  • the inputs are two indexes (i, j) of pointer on list A and B
  • the output is the maximum number of uncrossed lines

Edge Cases

  • Given 0 length of A and B
  • (i, j) already reaches to the end index i.e., i==len(A), j ==len(B)

Internal Process

  1. We would like to split the lists A and B when we find the same value in both list. In the example 2, first we will find 5 and draw the line.

  2. Add +1 to the non crossed line count

  3. Re-use the function for $A_2$ and $B_2$ as below.

  4. On the other hand, if we do not find the same value, we will run two scenarios: move i to one index ahead or move j to one index ahead.

  5. Compare the two scenario and take the larger number of non crossed lines.

split lists and use for a recursive function

Similar problems

Comments

Comments powered by Disqus