[Leetcode problems]1477. Find Two Non-overlapping Sub-arrays Each With Target Sum

Given an array of integers arr and an integer target.
You have to find two non-overlapping sub-arrays of 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 is minimum.
Return the minimum sum of the lengths of the two required sub-arrays, or return -1 if you cannot find such two sub-arrays.
 
Example 1:
Input: arr = [3,2,2,4,3], target = 3 Output: 2 Explanation: 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 = 7 Output: 2 Explanation: 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
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments