Uncrossed Lines - LeetCode

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

Now, we may draw connecting lines: a straight line connecting two numbers A[i] and B[j] such that:

• A[i] == B[j];
• The line we draw does not intersect any other connecting (non-horizontal) line.

Note that a connecting lines cannot intersect even at the endpoints: each number can only belong to one connecting line.

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

Let's split this into small sub problems

Example:

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

Let's loop through A and B and consider each element and check how many lines can be drawn

• if A[i] == B[i] then 1 + dp[i-1][j-1] i.e., how many lines are drawn before this
• else, we take the max of prev row(dp[i-1][j]) and column(dp[i][j-1])

Code

/**
 * @param {number[]} A
 * @param {number[]} B
 * @return {number}
 */
var maxUncrossedLines = function(A, B) {
    let m = A.length, n = B.length

    let dp = new Array(m + 1);

    for (let i = 0; i <= m; i++) {
        dp[i] = new Array(n + 1).fill(0);s
    }

    for(let i = 1; i <= m; i++) {
        for(let j = 1; j <= n; j++) {
            if(A[i - 1] == B[j - 1]) {
                dp[i][j] = 1 + dp[i - 1][j - 1]
            } else {
                dp[i][j] = Math.max(dp[i- 1][j], dp[i][j - 1])
            }
        }
    }

    return dp[m][n]
};