aboutsummaryrefslogtreecommitdiff
path: root/find_two_non_overlap_subarr.py
blob: 96508a8436b6e9e2139f36ae64cb845d4e7ca097 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
# 1477. Find Two Non-overlapping Sub-arrays Each With Target Sum
from itertools import accumulate

"""
you are given an array of integers 'arr' and an integer 'target'. you have to
find two non overlapping subarrays of 'arr' each with a sum equal to
'target'. there can be multiple answers so you have to finmd an answer where
the sum of the lengths of the two subarrays is minimum. return the minimum
sum of the lengths of the two required subarrays or return -1 if you cannot
find such two subarrays.
"""


class Solution(object):
    def minSumOfLengths(self, arr, target):
        """
        :type arr: List[int]
        :type target: int
        :rtype: int
        """
        prefix = {0: -1}
        curr_bestl = [float("inf")] * len(arr)
        ans, best = float("inf"), float("inf")
        for i, curr in enumerate(accumulate(arr)):
            if curr - target in prefix:
                end = prefix[curr - target]
                if end > -1:
                    ans = min(ans, i - end + curr_bestl[end])
                best = min(best, i - end)
            curr_bestl[i] = best
            prefix[curr] = i
        return -1 if ans == float("inf") else ans


if __name__ == "__main__":
    obj = Solution()
    print(obj.minSumOfLengths(arr=[3, 2, 2, 4, 3], target=3))
    print(obj.minSumOfLengths(arr=[7, 3, 4, 7], target=7))
    print(obj.minSumOfLengths(arr=[4, 3, 2, 6, 2, 3, 4], target=6))