aboutsummaryrefslogtreecommitdiff
path: root/find_two_non_overlap_subarr.py
diff options
context:
space:
mode:
Diffstat (limited to 'find_two_non_overlap_subarr.py')
-rw-r--r--find_two_non_overlap_subarr.py39
1 files changed, 39 insertions, 0 deletions
diff --git a/find_two_non_overlap_subarr.py b/find_two_non_overlap_subarr.py
new file mode 100644
index 0000000..96508a8
--- /dev/null
+++ b/find_two_non_overlap_subarr.py
@@ -0,0 +1,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))