LC-1477 Medium LeetCode

1477. Find Two Non-overlapping Sub-arrays Each With Target Sum

Array Hash Table Binary Search Dynamic Programming Sliding Window

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 36% Topics: Array, Hash Table, Binary Search, Dynamic Programming, Sliding Window

Reading material

Arrays & Hashing 12 min Binary Search 12 min 1-D Dynamic Programming 16 min

Reference solution (spoiler · python)

# Time:  O(n)
# Space: O(n)

class Solution(object):
    def minSumOfLengths(self, arr, target):
        """
        :type arr: List[int]
        :type target: int
        :rtype: int
        """
        prefix, dp = {0: -1}, [0]*len(arr)  # dp[i], min len of target subarray until i
        result = min_len = float("inf")
        accu = 0
        for right in xrange(len(arr)):
            accu += arr[right]
            prefix[accu] = right
            if accu-target in prefix:
                left = prefix[accu-target]
                min_len = min(min_len, right-left)
                if left != -1:
                    result = min(result, dp[left] + (right-left))
            dp[right] = min_len
        return result if result != float("inf") else -1

Solution from kamyu104/LeetCode-Solutions · MIT