Leetcode 1573 Solution

This article provides solution to leetcode question 1573 (find-two-non-overlapping-sub-arrays-each-with-target-sum)
Categories:
Tags:
Access this page by simply typing in "lcs 1573" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/find-two-non-overlapping-sub-arrays-each-with-target-sum

Solution

class Solution:
    def minSumOfLength(self, arr, target):
        m = {0: -1}

        opt = [sys.maxsize] * len(arr)
        ans = [sys.maxsize] * len(arr)

        s = 0
        for i, v in enumerate(arr):
            s += v

            if s - target in m:
                opt[i] = i - m[s - target]

            ans[i] = min(ans[i - 1], opt[i])
            m[s] = i

        return ans

    def minSumOfLengths(self, arr: List[int], target: int) -> int:
        a = self.minSumOfLength(arr, target)
        b = list(reversed(self.minSumOfLength(list(reversed(arr)), target)))

        ans = sys.maxsize
        for i in range(len(arr) - 1):
            ans = min(ans, a[i] + b[i + 1])

        return ans if ans < sys.maxsize else -1