Leetcode daily # 11.05.2023

[1035. Uncrossed Lines]

11.05.2023

1035. Uncrossed Lines medium

    fun maxUncrossedLines(nums1: IntArray, nums2: IntArray): Int {
        val cache = Array(nums1.size) { Array(nums2.size) { -1 } }
        val intersect = nums1.toSet().intersect(nums2.toSet())

        fun dfs(i: Int, j: Int, x: Int): Int {
            if (i == nums1.size || j == nums2.size) return 0
            val cached = cache[i][j]
            if (cached != -1) return cached
            val n1 = nums1[i]
            val n2 = nums2[j]
            val drawLine = if (n1 == x && n2 == x || n1 == n2) 1 + dfs(i + 1, j + 1, n1) else 0
            val skipTop = dfs(i + 1, j, x)
            val skipBottom = dfs(i, j + 1, x)
            val skipBoth = dfs(i + 1, j + 1, x)
            val startTop = if (intersect.contains(n1)) dfs(i + 1, j, n1) else 0
            val startBottom = if (intersect.contains(n2)) dfs(i, j + 1, n2) else 0
            val res = maxOf(
                drawLine,
                maxOf(drawLine, skipTop, skipBottom),
                maxOf(skipBoth, startTop, startBottom)
            )
            cache[i][j] = res
            return res
        }
        return dfs(0, 0, 0)
    }

blog post

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/209

Intuition

Consider the case:

2 5 1 2 5
2 2 2 1 1 1 5 5 5

When we draw all the possible lines, we see that there is a choice to draw line 2-2 or four lines 1-1 or three 5-5 in the middle. Suffix lines 5-5 and prefix lines 2-2 are optimal already and can be cached as a result.
To find an optimal choice, we can use DFS.
We can prune some impossible combinations by precomputing the intersected numbers and considering them only.

Approach

• use an array for the faster cache instead of HashMap

• for the intersection, there is an intersect method in Kotlin

Complexity

• Time complexity:
  O(n^2)

• Space complexity:
  O(n^2)