Uncrossed Lines

class Solution {
public:
    int maxNonCrossingLines(vector<int>& A, vector<int>& B) {
        int sizeA = A.size(), sizeB = B.size();
        vector<int> curr(sizeB + 1), last(sizeB + 1);
    
        for (int i = 1; i <= sizeA; i++) {
            for (int j = 1; j <= sizeB; j++) {
                if (A[i - 1] == B[j - 1]) {
                    curr[j] = 1 + last[j - 1];
                } else {
                    curr[j] = max(curr[j - 1], last[j]);
                }
            }
            last = curr;
        }
    
        return curr[sizeB];
    }
};

The provided C++ solution aims to solve the problem of finding the maximum number of non-crossing lines that can be drawn between the elements of two integer arrays. This problem essentially maps to finding the longest common subsequence (LCS) between the two arrays.

Here's a breakdown of the code's approach:

• A solution class Solution is defined containing the function maxNonCrossingLines.
• The function receives two integer vectors, A and B.
• sizeA and sizeB store the sizes of vectors A and B respectively.
• Two integer vectors, curr and last, each of size sizeB + 1, are used to store the current and the previous lengths of LCS up to each index.
• The outer loop runs through each element in vector A, and the inner loop runs through each element in vector B.
• During the traversal, if the elements A[i - 1] and B[j - 1] match:
  • curr[j] is set to 1 + last[j - 1], updating it to the length of LCS found so far including the current match.
• If there is no match:
  • curr[j] is set to the maximum of the left (curr[j - 1]) and the upper values (last[j]) to ensure the longest sequence length is carried forward.
• After each inner loop iteration, last is updated to the current values of curr to preserve the context for the next iteration.
• Finally, the function returns curr[sizeB] which contains the length of the longest non-crossing lines (LCS) after considering all elements.

This algorithm efficiently computes the maximum number of non-crossing lines with a time complexity of O(n*m), where n and m are the sizes of vectors A and B, respectively, using a dynamic programming approach that uses two rolling arrays to keep the space complexity linear relative to the size of vector B.

class Solution {
    public int maximumUncrossedLines(int[] A, int[] B) {
        int lenA = A.length;
        int lenB = B.length;
    
        int[] current = new int[lenB + 1];
        int[] previous = new int[lenB + 1];
    
        for (int i = 1; i <= lenA; i++) {
            for (int j = 1; j <= lenB; j++) {
                if (A[i - 1] == B[j - 1]) {
                    current[j] = 1 + previous[j - 1];
                } else {
                    current[j] = Math.max(current[j - 1], previous[j]);
                }
            }
            previous = current.clone();
        }
            
        return current[lenB];
    }
}

The provided Java solution effectively tackles the problem of finding maximum number of uncrossed lines between two arrays, which can be visualized as a variant of the Longest Common Subsequence problem. Here’s a concise summary of how this code works:

• Initialize two integer arrays, current and previous, sized one more than the length of array B (lenB + 1), to store intermediate results for dynamic programming.
• Employ a nested loop where the outer loop iterates through each element of array A, and the inner loop iterates through each element of array B.
• Inside the inner loop, check if the current elements of A and B, A[i-1] and B[j-1], are equal:
  • If they are, set current[j] to 1 + previous[j - 1] to build on the matched sequence.
  • If not, set current[j] to the maximum of current[j-1] or previous[j] to carry forward the maximum uncrossed lines count without extending the sequence.
• After completing each inner loop iteration, copy the current array to the previous array with current.clone() to update the states for the next iteration.
• The final result, after looping through both arrays, will be stored in current[lenB], which represents the maximum number of uncrossed lines between the two arrays.

This code utilizes dynamic programming efficiently by using only two arrays and updating them iteratively, minimizing space complexity while ensuring the optimal solution is computed.