~/leetcode$cat1477. Find Two Non-overlapping Sub-arrays Each With Target Sum

This seems like a sliding window problem - we can just slide the window from the start of the list to the end, checking whether or not the current window sums to the target value.

I think we can keep track of two numbers: the current sum of the lengths of the subarrays and the length of the current longest subarray that we are keeping track of (remember we only have to keep track of 2).

When we are keeping track of two subarrays and we come across a new one:

• if the length is shorter than the current longest subarray, we will replace the two (subtract that length from the current total and add the new subarray length)
• calculate the new longest subarray length while doing this and save that.

If we are keeping track of two subarrays once we are done, return the sum of the lengths of the subarrays. If not, we have not found enough subarrays so we return -1.

Jokes, this doesn’t work, the problem says NON-OVERLAPPING… oman.

Since we are trying to find TWO non-overlapping, we can effectively try to cut the list in two somewhere and add the minimum subarrays in each half. This is kind of like a DP problem because we can construct a prefix and suffix list where prefix[i] is the length of the smallest subarray up to and excluding i and the suffix list is the other way (from i until the end of the list).

Then we are trying to find i where prefix[i] + suffix[i] is minimised and return that sum.

I think that original way with the sliding window works for computing the prefix and suffix list. So basically the non-overlapping condition just wraps this prefix, suffix stuff on top of it.

class Solution:
    def minSumOfLengths(self, arr: List[int], target: int) -> int:
        something
        n = len(arr)
        if n == 1: return -1

        prefix = [inf] * n
        suffix = [inf] * n

        # compute the prefix
        l = 0
        currentWindow = arr[0]
        if currentWindow == target:
            prefix[1] = 1

        for r in range(1, n - 1):
            currentWindow += arr[r]
            while currentWindow > target and l < r:
                currentWindow -= arr[l]
                l += 1

            newLength = inf
            if currentWindow == target:
                newLength = r - l + 1

            prefix[r + 1] = min(prefix[r], newLength)

        # compute the suffix
        r = n - 1
        currentWindow = arr[n - 1]
        if currentWindow == target:
            suffix[n - 1] = 1

        for l in range(n - 2, -1, -1):
            currentWindow += arr[l]
            while currentWindow > target and r > l:
                currentWindow -= arr[r]
                r -= 1

            newLength = inf
            if currentWindow == target:
                newLength = r - l + 1

            suffix[l] = min(suffix[l + 1], newLength)

        # traverse
        minLength = inf
        for i in range(n):
            length = prefix[i] + suffix[i]
            minLength = min(minLength, length)

        if minLength == inf:
            return -1
        return minLength

Time Complexity: O(n)

Space Complexity: O(n)

Time Taken: forgot to keep track

Runtime: 240 ms

Memory: 31.1 MB

Tests Passed: 61/61