[
intervals
sort
binary search
two pointers
accumulate
]
BinarySearch 0603 Two Non-Overlapping Lists With Target Sums
Problem statement
https://binarysearch.com/problems/Two-Non-Overlapping-Lists-With-Target-Sums/
Solution
First, find all intervals with sum k
, using cumulative sums. It can be shown that there will be not more than n
of them: indeed for each end if we have two intervals, they will be overlapping. Then we use problem BinarySearch 0655 Minimum Size of Two Non-Overlapping Intervals to shortest sum of two non-overlapping intervals.
Complexity
It is O(n log n)
for time and space. In fact it can be made O(n)
, because when we create I
we can make it already sorted (now it is sorted by ends, if we reverse array)
Code
class Solution:
def solve(self, nums, k):
d, I = {0: -1}, []
for i, x in enumerate(accumulate(nums)):
if x - k in d:
I += [[d[x - k] + 1, i]]
d[x] = i
if len(I) <= 1: return -1
I = sorted(I)
acc = list(accumulate([y - x for x, y in I[::-1]], min))[::-1]
ans = float("inf")
for x, y in I:
idx = bisect.bisect(I, [y, float("inf")])
if idx < len(I):
ans = min(ans, y - x + 1 + acc[idx] + 1)
return ans if ans != float("inf") else -1