Find Two Non-overlapping Sub-arrays Each With Target Sum

Medium

Google

2 views

Topics:

ArraysSliding Windows

You are given an array of integers arr and an integer target. You have to find two non-overlapping sub-arrays of arr each with a 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.

For example:

arr = [3,2,2,4,3], target = 3. The expected output is 2 because only two sub-arrays have a sum of 3 which are [3] and [3]. The sum of their lengths is 2.
arr = [7,3,4,7], target = 7. The expected output is 2 because 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.
arr = [4,3,2,6,2,3,4], target = 6. The expected output is -1 because we have only one sub-array of sum = 6.

Could you provide an algorithm to solve this problem efficiently, considering time and space complexity? What are the edge cases that need to be handled?

Find Two Non-overlapping Sub-arrays Each With Target Sum

Medium

Google

2 views

Topics:

ArraysSliding Windows

For example:

arr = [3,2,2,4,3], target = 3. The expected output is 2 because only two sub-arrays have a sum of 3 which are [3] and [3]. The sum of their lengths is 2.
arr = [7,3,4,7], target = 7. The expected output is 2 because 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.
arr = [4,3,2,6,2,3,4], target = 6. The expected output is -1 because we have only one sub-array of sum = 6.

Could you provide an algorithm to solve this problem efficiently, considering time and space complexity? What are the edge cases that need to be handled?

Solution

Naive Solution

The brute force approach would involve finding all possible sub-arrays with the target sum and then iterating through all pairs of such sub-arrays to check for non-overlapping conditions. The main disadvantage of this approach is its high time complexity.

Optimal Solution

A more efficient solution involves using a sliding window technique to find all sub-arrays with the target sum. We can store the minimum length of a sub-array ending at each index. Then, we iterate through the array again, using a sliding window to find another sub-array with the target sum. While doing so, we check the minimum length of a non-overlapping sub-array that appears before the current window. The minimum sum of lengths can be updated accordingly.

Edge Cases

If no sub-array with the target sum exists, return -1.
If only one such sub-array exists, return -1.
Consider cases where target is negative or array contains negative numbers (if the problem statement allows it).
Handle cases of empty array.

Code

def minSumOfLengths(arr, target):
    n = len(arr)
    min_len = float('inf')
    left = [float('inf')] * n
    curr_sum = 0
    start = 0
    min_so_far = float('inf')

    for i in range(n):
        curr_sum += arr[i]
        while curr_sum > target:
            curr_sum -= arr[start]
            start += 1
        if curr_sum == target:
            length = i - start + 1
            min_so_far = min(min_so_far, length)
        left[i] = min_so_far

    min_sum = float('inf')
    curr_sum = 0
    end = n - 1
    min_so_far = float('inf')

    for i in range(n - 1, -1, -1):
        curr_sum += arr[i]
        while curr_sum > target:
            curr_sum -= arr[end]
            end -= 1
        if curr_sum == target:
            length = end - i + 1
            if i > 0 and left[i - 1] != float('inf'):
                min_sum = min(min_sum, length + left[i - 1])

    return min_sum if min_sum != float('inf') else -1

Big O Analysis

Time Complexity: O(n), where n is the length of the input array. We iterate through the array at most twice.
Space Complexity: O(n), due to the auxiliary array left.

Solution

Naive Solution

Optimal Solution

Edge Cases

If no sub-array with the target sum exists, return -1.
If only one such sub-array exists, return -1.
Consider cases where target is negative or array contains negative numbers (if the problem statement allows it).
Handle cases of empty array.

Code

def minSumOfLengths(arr, target):
    n = len(arr)
    min_len = float('inf')
    left = [float('inf')] * n
    curr_sum = 0
    start = 0
    min_so_far = float('inf')

    for i in range(n):
        curr_sum += arr[i]
        while curr_sum > target:
            curr_sum -= arr[start]
            start += 1
        if curr_sum == target:
            length = i - start + 1
            min_so_far = min(min_so_far, length)
        left[i] = min_so_far

    min_sum = float('inf')
    curr_sum = 0
    end = n - 1
    min_so_far = float('inf')

    for i in range(n - 1, -1, -1):
        curr_sum += arr[i]
        while curr_sum > target:
            curr_sum -= arr[end]
            end -= 1
        if curr_sum == target:
            length = end - i + 1
            if i > 0 and left[i - 1] != float('inf'):
                min_sum = min(min_sum, length + left[i - 1])

    return min_sum if min_sum != float('inf') else -1

Big O Analysis

Time Complexity: O(n), where n is the length of the input array. We iterate through the array at most twice.
Space Complexity: O(n), due to the auxiliary array left.