{x}
blog image

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

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.

 

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.

Example 3:

Input: arr = [4,3,2,6,2,3,4], target = 6
Output: -1
Explanation: We have only one sub-array of sum = 6.

 

Constraints:

  • 1 <= arr.length <= 105
  • 1 <= arr[i] <= 1000
  • 1 <= target <= 108

Solution Explanation:

This problem asks to find two non-overlapping subarrays within a given array arr, each having a sum equal to the given target. The goal is to minimize the total length of these two subarrays.

The solution employs a dynamic programming approach combined with a hashmap to efficiently track subarray sums and their lengths.

Algorithm:

  1. Initialization:

    • A hashmap d stores cumulative sums and their corresponding indices. It's initialized with {0: 0} because a cumulative sum of 0 occurs at index 0.
    • An array f of size n+1 (where n is the length of arr) stores the minimum length of a subarray ending at each index i with a sum equal to target. It's initialized with infinity except for f[0] = 0 (no subarray means length 0).
    • ans stores the minimum total length of the two subarrays and is initialized with infinity.

  2. Iteration:

    • The code iterates through the array arr using a cumulative sum s.
    • For each index i, it updates f[i] to be the minimum between its previous value and the length of the current subarray ending at i with a sum equal to target.
    • If s - target exists in the hashmap d, it means there's a subarray ending at index j (retrieved from d[s - target]) with a sum of target. This is the first subarray. The length of this subarray is i - j. The second subarray's length can be found from the minimum length of a subarray ending before index j, which is f[j]. The minimum total length is then f[j] + i - j. The minimum among these total lengths is updated in ans.
    • The current cumulative sum s and its index i are added to the hashmap d.

  3. Result:

    • After iterating through the array, if ans is greater than n (meaning no two such subarrays were found), -1 is returned. Otherwise, ans (the minimum sum of lengths) is returned.

Time Complexity: O(n), where n is the length of the input array. The code iterates through the array once. Hashmap lookups and insertions are on average O(1).

Space Complexity: O(n) due to the hashmap d and the array f, which both store n elements at most.

Example Walkthrough (Example 1: arr = [3,2,2,4,3], target = 3):

  1. d = {0: 0}, f = [0, inf, inf, inf, inf, inf], ans = inf, s = 0.
  2. Iteration 1 (i=1, v=3): s = 3, s - target = 0, j = 0, f[1] = min(inf, 1) = 1, ans = min(inf, f[0] + 1) = 1, d = {0: 0, 3: 1}.
  3. Iteration 2 (i=2, v=2): s = 5, s - target is not in d.
  4. Iteration 3 (i=3, v=2): s = 7, s - target is not in d.
  5. Iteration 4 (i=4, v=4): s = 11, s - target is not in d.
  6. Iteration 5 (i=5, v=3): s = 14, s - target = 11, which is not in d. However, s - target = 3 which is in d, so j = 1, f[5] = min(f[4], 5-1) = 4. ans = min(1, f[1] + 5 - 1) = 1.
  7. Finally, ans = 2 (because there are two subarrays [3] and [3], total length 2)

The code provided in different languages implements this algorithm. The key is understanding the interplay between the cumulative sum, the hashmap to find previous subarray sums, and dynamic programming to track minimum subarray lengths.