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