We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

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

Difficulty: Medium

Problem Description

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.

Key Insights

  • The problem requires finding two non-overlapping sub-arrays with a specific sum.
  • A sliding window approach can be used to find sub-arrays with the target sum efficiently.
  • Care must be taken to ensure that the found sub-arrays do not overlap, which means tracking indices properly.
  • The use of a hash table can help in storing the minimum lengths of sub-arrays found so far.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

To solve this problem, we will use a sliding window approach along with a hash table to store the minimum lengths of sub-arrays that sum to the target. We will first iterate through the array to find all sub-arrays that sum to the target and store their lengths in a hash table. Then, for each of these sub-arrays, we will check for any previously found sub-arrays that do not overlap and keep track of the minimum sum of their lengths.

Code Solutions

def minSumOfLengths(arr, target):
    n = len(arr)
    min_length = [float('inf')] * n
    current_sum = 0
    left = 0
    result = float('inf')

    # Find all sub-arrays with sum equal to target
    for right in range(n):
        current_sum += arr[right]

        while current_sum > target:
            current_sum -= arr[left]
            left += 1
        
        if current_sum == target:
            sub_array_length = right - left + 1
            min_length[right] = sub_array_length if right == 0 else min(min_length[right - 1], sub_array_length)
        
        if right > 0:
            result = min(result, min_length[left - 1] + sub_array_length)

    return result if result != float('inf') else -1
← Back to All Questions