Given an array of integers`arr`

and an integer`target`

. You have to findtwo non-overlapping sub-arraysof`arr`

each with sum equal`target`

. There can be multiple answers so you have to find an answer where the sum of the lengths of the two sub-arrays isminimum. Returnthe minimum sum of the lengthsof the two required sub-arrays, or returnif you cannot find such two sub-arrays.-1Example 1:Input:arr = [3,2,2,4,3], target = 3Output:2Explanation:Only two sub-arrays have sum = 3 ([3] and [3]). The sum of their lengths is 2.Example 2:Input:arr = [7,3,4,7], target = 7Output:2Explanation:Although we have three non-overlapping sub-arrays of sum = 7 ([7], [3,4] and [7]), but we will choose the first and third sub-arrays as the sum of their lengths is 2.

This question first appeared in the Leetcode Biweekly Contest 28. While I was in the contest, I came up with the brute force solution first and improved it step by step, but kept getting `TLE`

. This post will walk through this journey from the naive approach to the most voted solution in the Discuss by @chuan-chih. The O(n) solution will be at the end, so feel free to jump there if you want to skip the optimization process.

#### Brute force solution – O(n^2)

We can divide the problem into two parts: first, we need to find all the subarrays summed to `target`

, then we need to find the legal pairs with minimal lengths.

To find the qualified subarrays, we can use a nested for-loop with O(n^2).

```
opts = [] # used to store the subarrays
n = len(arr)
for i in range(n):
sum = 0
for j in range(i,n):
sum += arr[j]
if sum > target:
break
if sum == target:
opts.append([i,j])
break
```

After getting the subarrays, we can sort them by their lengths, and use another nested for-loop to find the minimal lengths of legal pairs.

```
opts.sort(key=lambda x: x[1]-x[0])
m = len(opts)
ret = float('inf')
for i in range(m):
for j in range(i+1,m):
# if not overlapping
if opts[i][1] < opts[j][0] or opts[i][0] > opts[j][1]:
ret = min(ret,(opts[i][1]-opts[i][0]+1)+(opts[j][1]-opts[j][0]+1))
break
```

#### Optimisation – O(n)

When looking for the qualified subarrays, we can use prefix-sum and HashSet to achieve O(n). More specifically, we would count the prefix sum and save the `(sum,index)`

pair into a HashSet. At the same time, if we find `sum-target`

in the HashSet, we know there’s one qualified subarray and its boundary. Notably, the Python Standard Library provides a library to calculate the prefix sum as `itertools.accumulate(arr)`

.

After getting the subarrays, we implement a 1D array `lengths`

so that` lengths[i]`

indicates the shortest length of the qualified subarrays ending up to `i`

. I’d personally treat this as a Dynamic Programming as it avoids massive repeated computations to find the non-overlapping pairs.

```
def minSumOfLengths(self, arr: List[int], target: int) -> int:
prefix = {0:-1}
lengths = [float('inf')] * len(arr)
ret = shortest = float('inf')
for i,val in enumerate(itertools.accumulate(arr)):
if val-target in prefix:
ind = prefix[val-target]
if ind > -1:
ret = min(ret,i-ind + lengths[ind])
shortest = min(shortest,i-ind)
lengths[i] = shortest
prefix[val] = i
return ret if ret != float('inf') else -1
```

#### More

Inspired by @ping_pong, we could notice that `arr[i]`

is always positive, therefore we can use two pointer sliding window instead of HashSet to find the qualified subarray. To be more specific, once we find that `sum(arr[left...right])>target`

, we can simply move `left`

towards `right`

until `sum(arr[left...right])<=target`

```
def minSumOfLengths(self, arr: List[int], target: int) -> int:
lengths = [float('inf')] * len(arr)
ret = shortest = float('inf')
left = s = 0 # using left and right as sliding window to find subarrays
for right,val in enumerate(arr):
s += val
while s > target:
s -= arr[left]
left += 1
if s == target:
ret = min(ret,(right-left+1) + lengths[left-1])
shortest = min(shortest,right-left+1)
lengths[right] = shortest
return ret if ret != float('inf') else -1
```