Problem Description

You are given an array of integers arr and an integer target.

Your task is to find two non-overlapping subarrays from arr where each subarray has a sum equal to target. Since there can be multiple valid pairs of subarrays, you need to find the pair where the sum of the lengths of the two subarrays is minimum.

A subarray is a contiguous sequence of elements from the array. Two subarrays are non-overlapping if they don't share any elements at the same indices.

Return the minimum sum of the lengths of the two required subarrays. If it's not possible to find two such non-overlapping subarrays, return -1.

For example:

• If arr = [3,2,2,4,3] and target = 3, you can find subarrays [3] (length 1) and [3] (length 1), giving a minimum sum of lengths = 2
• If arr = [7,3,4,7] and target = 7, you can find subarrays [7] (length 1) and [3,4] (length 2), giving a minimum sum of lengths = 3
• If no two non-overlapping subarrays with sum equal to target exist, return -1

Intuition

The key insight is that we need to find two non-overlapping subarrays with sum equal to target, and we want to minimize their combined length. This suggests we should track the shortest valid subarray we've seen so far as we traverse the array.

As we move through the array from left to right, at each position i, we can consider two scenarios:

1. The current position could be the end of a subarray with sum equal to target
2. We might have already found a valid subarray to the left of the current position

To efficiently find subarrays with a specific sum, we can use the prefix sum technique. If we maintain a running sum s as we traverse the array, then a subarray from index j to i has sum equal to target if s[i] - s[j] = target, which means s[j] = s[i] - target.

Using a hash table to store the positions where each prefix sum occurs allows us to quickly check if there's a valid starting point j for a subarray ending at position i.

The dynamic programming aspect comes from maintaining f[i], which represents the minimum length of any subarray with sum equal to target found in the first i elements. This helps us keep track of the best (shortest) subarray we've found so far on the left side.

When we find a new valid subarray from position j to i, we can:

• Update f[i] to be the minimum of the previous best and the current subarray's length (i - j)
• Check if combining this new subarray with the best subarray found before position j (which is f[j]) gives us a better overall answer

This approach ensures we consider all possible pairs of non-overlapping subarrays while maintaining the minimum combined length throughout the traversal.

Learn more about Binary Search, Dynamic Programming and Sliding Window patterns.

Solution Approach

We implement the solution using hash table, prefix sum, and dynamic programming techniques.

Data Structures:

• Hash table d to store the most recent position where each prefix sum appears, initialized with d[0] = 0
• Array f of size n+1 where f[i] represents the minimum length of a subarray with sum equal to target among the first i elements, initialized with infinity
• Variable s to maintain the running prefix sum
• Variable ans to track the minimum sum of lengths, initialized with infinity

Algorithm Steps:

1. Initialize the hash table: Set d[0] = 0 to handle cases where the subarray starts from index 0.

2. Iterate through the array: For each element at position i (1-indexed):

   • Add the current element to the prefix sum: s += arr[i-1]
   • Copy the previous best: f[i] = f[i-1]

3. Check for valid subarray ending at position i:

   • If s - target exists in the hash table d, it means there's a subarray with sum equal to target
   • Let j = d[s - target] be the starting position of this subarray
   • The length of this subarray is i - j

4. Update the dynamic programming state:

   • Update f[i] to be the minimum of its current value and the new subarray length: f[i] = min(f[i], i - j)
   • This ensures f[i] always holds the shortest valid subarray found in the first i elements

5. Update the answer:

   • Consider pairing the current subarray (from j to i) with the best subarray found before position j
   • The combined length would be f[j] + (i - j)
   • Update the answer: ans = min(ans, f[j] + i - j)

6. Update the hash table: Store the current position for the current prefix sum: d[s] = i

7. Return the result:

   • If ans is still greater than the array length n, it means we couldn't find two valid subarrays, so return -1
   • Otherwise, return ans

The algorithm runs in O(n) time complexity with O(n) space complexity, efficiently finding the minimum sum of lengths of two non-overlapping subarrays with the target sum.

Example Walkthrough

Let's walk through the solution with arr = [3, 2, 2, 4, 3] and target = 3.

Initial Setup:

• n = 5
• d = {0: 0} (hash table for prefix sums and their positions)
• f = [0, ∞, ∞, ∞, ∞, ∞] (minimum subarray lengths)
• s = 0 (prefix sum)
• ans = ∞ (minimum combined length)

Iteration 1 (i=1, element=3):

• Update prefix sum: s = 0 + 3 = 3
• Copy previous best: f[1] = f[0] = 0
• Check if s - target = 3 - 3 = 0 exists in d: YES, at position j = 0
• Subarray found: from position 0 to 1, length = 1 - 0 = 1
• Update f[1] = min(∞, 1) = 1
• Update answer: ans = min(∞, f[0] + 1) = min(∞, 0 + 1) = 1 (but we need 2 subarrays, so this just tracks potential)
• Update hash table: d[3] = 1
• State: d = {0: 0, 3: 1}, f = [0, 1, ∞, ∞, ∞, ∞]

Iteration 2 (i=2, element=2):

• Update prefix sum: s = 3 + 2 = 5
• Copy previous best: f[2] = f[1] = 1
• Check if s - target = 5 - 3 = 2 exists in d: NO
• No new subarray found
• Update hash table: d[5] = 2
• State: d = {0: 0, 3: 1, 5: 2}, f = [0, 1, 1, ∞, ∞, ∞]

Iteration 3 (i=3, element=2):

• Update prefix sum: s = 5 + 2 = 7
• Copy previous best: f[3] = f[2] = 1
• Check if s - target = 7 - 3 = 4 exists in d: NO
• No new subarray found
• Update hash table: d[7] = 3
• State: d = {0: 0, 3: 1, 5: 2, 7: 3}, f = [0, 1, 1, 1, ∞, ∞]

Iteration 4 (i=4, element=4):

• Update prefix sum: s = 7 + 4 = 11
• Copy previous best: f[4] = f[3] = 1
• Check if s - target = 11 - 3 = 8 exists in d: NO
• No new subarray found
• Update hash table: d[11] = 4
• State: d = {0: 0, 3: 1, 5: 2, 7: 3, 11: 4}, f = [0, 1, 1, 1, 1, ∞]

Iteration 5 (i=5, element=3):

• Update prefix sum: s = 11 + 3 = 14
• Copy previous best: f[5] = f[4] = 1
• Check if s - target = 14 - 3 = 11 exists in d: YES, at position j = 4
• Subarray found: from position 4 to 5, length = 5 - 4 = 1
• Update f[5] = min(1, 1) = 1
• Update answer: ans = min(1, f[4] + 1) = min(1, 1 + 1) = min(1, 2)
• Wait, ans was previously 1, but that was when we only had one subarray
• Actually, ans = min(∞, f[4] + (5-4)) = min(∞, 1 + 1) = 2
• This gives us two subarrays: one with length 1 found before position 4, and current subarray [3] with length 1
• Update hash table: d[14] = 5
• Final state: ans = 2

Result: The minimum sum of lengths is 2, coming from subarrays [3] at index 0 (length 1) and [3] at index 4 (length 1).

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the input array. The algorithm makes a single pass through the array with a for loop that iterates through each element exactly once. Within each iteration, all operations are constant time: dictionary lookups (s - target in d), dictionary insertions (d[s] = i), array access and updates (f[i]), and arithmetic operations. Therefore, the overall time complexity is linear.

The space complexity is O(n), where n is the length of the input array. The algorithm uses:

• A dictionary d that can store up to n + 1 key-value pairs (one for each possible prefix sum including the initial 0)
• An array f of size n + 1 to store the minimum subarray lengths
• A few scalar variables (s, n, ans) which use O(1) space

The dominant space usage comes from the dictionary and array, both of which scale linearly with the input size, resulting in O(n) space complexity.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Not Handling the Case Where Multiple Indices Have the Same Prefix Sum

The Pitfall: The current implementation overwrites the previous index when the same prefix sum appears multiple times: cumsum_to_index[cumulative_sum] = current_index. This can lead to incorrect results because we might miss valid subarrays that could form better combinations.

Example Scenario: Consider arr = [1, 1, 1, 2, 2, 2, 4, 4] with target = 4:

• At index 3, cumulative sum = 3
• At index 6, cumulative sum = 9
• At index 7, cumulative sum = 13
• At index 8, cumulative sum = 17

If we later encounter a position where we need cumulative sum 9 to form a subarray with sum 4, we'll only have the latest index stored, potentially missing a shorter subarray.

Solution: While the current approach works correctly for this specific problem (because we always want the most recent occurrence to minimize subarray length), it's important to understand why:

• When we encounter cumulative_sum - target in the dictionary, we want the rightmost (most recent) occurrence
• This gives us the shortest possible subarray ending at the current position
• The algorithm naturally handles this by overwriting with the latest index

2. Confusion Between 0-Based and 1-Based Indexing

The Pitfall: The code uses 1-based indexing for the iteration (enumerate(arr, 1)) but the array min_length and dictionary operations mix both conventions, which can be confusing and error-prone when modifying the code.

Solution: Stick to one indexing convention throughout:

def minSumOfLengths(self, arr: List[int], target: int) -> int:
    # Use 0-based indexing consistently
    cumsum_to_index = {0: -1}  # -1 represents before the array starts
    cumulative_sum = 0
    n = len(arr)
  
    # min_length[i] represents minimum length found up to index i (inclusive)
    min_length = [float('inf')] * n
    min_total_length = float('inf')
  
    for i in range(n):
        cumulative_sum += arr[i]
      
        # Carry forward from previous index
        if i > 0:
            min_length[i] = min_length[i - 1]
      
        required_sum = cumulative_sum - target
        if required_sum in cumsum_to_index:
            start_index = cumsum_to_index[required_sum]
            current_subarray_length = i - start_index
          
            min_length[i] = min(min_length[i], current_subarray_length)
          
            # Combine with best subarray before start_index
            if start_index >= 0:
                combined_length = min_length[start_index] + current_subarray_length
            else:
                combined_length = current_subarray_length
          
            min_total_length = min(min_total_length, combined_length)
      
        cumsum_to_index[cumulative_sum] = i
  
    return -1 if min_total_length > n else min_total_length

3. Not Properly Initializing the First Element of min_length Array

The Pitfall: If the very first element equals the target, we need to ensure min_length[0] or min_length[1] (depending on indexing) is properly set. The line min_length[current_index] = min_length[current_index - 1] could propagate infinity values incorrectly.

Solution: The current implementation handles this correctly because:

• It checks for valid subarrays after copying the previous value
• It updates min_length[current_index] if a valid subarray is found
• The initialization with infinity ensures no invalid comparisons

However, for clarity, you could explicitly handle the first element:

if current_index == 1:
    min_length[current_index] = float('inf')
else:
    min_length[current_index] = min_length[current_index - 1]