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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

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

Number: 1573

Difficulty: Medium

Paid? No

Companies: Google

Problem Description

Given an array of integers and a target sum, find two non-overlapping sub-arrays each whose sum equals the target. The goal is to minimize the sum of the lengths of these two sub-arrays. If no such pair exists, return -1.

Key Insights

  • Use a sliding window because the array consists of positive integers.
  • Maintain a dynamic programming (dp) array to record the minimum length of any valid sub-array ending at or before each index.
  • As a valid sub-array is found using the sliding window, check the dp array for a candidate sub-array in the left portion that does not overlap with the current one.
  • Update the result minimizing the combined lengths of the two sub-arrays.

Space and Time Complexity

Time Complexity: O(n) - Single (or two) linear pass(es) through the array. Space Complexity: O(n) - For maintaining the dp array that stores minimal sub-array lengths.

Solution

The solution is based on a sliding window approach to identify sub-arrays that sum to the target. As we iterate with the window, we keep the best candidate (smallest length sub-array) up to the current index in a dp array. When we find a valid sub-array with sum equal to the target, we then check if a previous non-overlapping valid sub-array exists by looking at dp[left-1]. If found, we update the minimum total length. This technique efficiently ensures that the sub-arrays do not overlap and that their total length is minimized.

Code Solutions

# Python solution using sliding window and dynamic programming

def minSumOfLengths(arr, target):
    n = len(arr)
    # dp[i] holds the minimum length of a subarray ending on or before index i with a sum equal to target
    dp = [float('inf')] * n
    best = float('inf')
    current_sum = 0
    left = 0
    result = float('inf')
    
    for right in range(n):
        current_sum += arr[right]
        # Shrink the window until the sum is less than or equal to target
        while current_sum > target and left <= right:
            current_sum -= arr[left]
            left += 1
        # When a valid subarray is found (sum equals target)
        if current_sum == target:
            current_length = right - left + 1
            # If there is a valid subarray ending before the current one, update result
            if left > 0 and dp[left - 1] != float('inf'):
                result = min(result, dp[left - 1] + current_length)
            best = min(best, current_length)
        dp[right] = best if right == 0 else min(dp[right - 1], best)
    
    return result if result != float('inf') else -1

# Example usage:
if __name__ == "__main__":
    print(minSumOfLengths([3,2,2,4,3], 3))  # Expected output: 2
← Back to All Questions