1035. Uncrossed Lines - Explanation

1. Recursion

class Solution:
    def maxUncrossedLines(self, nums1: List[int], nums2: List[int]) -> int:
        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)
            return max(dfs(i, j + 1), dfs(i + 1, j))

        return dfs(0, 0)

Time & Space Complexity

Time complexity: $O(2 ^ {n + m})$
Space complexity: $O(n + m)$ for recursion stack.

Where $n$ and $m$ are the sizes of the arrays $nums1$ and $nums2$ respectively.

2. Dynamic Programming (Top-Down)

class Solution:
    def maxUncrossedLines(self, nums1: List[int], nums2: List[int]) -> int:
        dp = {}

        def dfs(i, j):
            if i == len(nums1) or j == len(nums2):
                return 0

            if (i, j) in dp:
                return dp[(i, j)]

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

            return dp[(i, j)]

        return dfs(0, 0)

Time & Space Complexity

Time complexity: $O(n * m)$
Space complexity: $O(n * m)$

Where $n$ and $m$ are the sizes of the arrays $nums1$ and $nums2$ respectively.

3. Dynamic Programming (Bottom-Up)

class Solution:
    def maxUncrossedLines(self, nums1: List[int], nums2: List[int]) -> int:
        n, m = len(nums1), len(nums2)
        dp = [[0] * (m + 1) for _ in range(n + 1)]

        for i in range(n):
            for j in range(m):
                if nums1[i] == nums2[j]:
                    dp[i + 1][j + 1] = 1 + dp[i][j]
                else:
                    dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j])

        return dp[n][m]

Time & Space Complexity

Time complexity: $O(n * m)$
Space complexity: $O(n * m)$

Where $n$ and $m$ are the sizes of the arrays $nums1$ and $nums2$ respectively.

4. Dynamic Programming (Space Optimized)

class Solution:
    def maxUncrossedLines(self, nums1: List[int], nums2: List[int]) -> int:
        prev = [0] * (len(nums2) + 1)

        for i in range(len(nums1)):
            dp = [0] * (len(nums2) + 1)
            for j in range(len(nums2)):
                if nums1[i] == nums2[j]:
                    dp[j + 1] = 1 + prev[j]
                else:
                    dp[j + 1] = max(dp[j], prev[j + 1])
            prev = dp

        return prev[len(nums2)]

Time & Space Complexity

Time complexity: $O(n * m)$
Space complexity: $O(m)$

Where $n$ and $m$ are the sizes of the arrays $nums1$ and $nums2$ respectively.

5. Dynamic Programming (Optimal)

class Solution:
    def maxUncrossedLines(self, nums1: List[int], nums2: List[int]) -> int:
        n, m = len(nums1), len(nums2)
        if m > n:
            n, m = m, n
            nums1, nums2 = nums2, nums1

        dp = [0] * (m + 1)

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

        return dp[m]

Time & Space Complexity

Time complexity: $O(n * m)$
Space complexity: $O(min(n, m))$

Where $n$ and $m$ are the sizes of the arrays $nums1$ and $nums2$ respectively.