Watch 10 video solutions for Find Two Non-overlapping Sub-arrays Each With Target Sum, a medium level problem involving Array, Hash Table, Binary Search. This walkthrough by Happy Coding has 4,664 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 1051 <= arr[i] <= 10001 <= target <= 108Problem Overview: You get an integer array and a target value. The task is to find two non-overlapping subarrays whose sums equal the target and return the minimum combined length of those two subarrays. If no such pair exists, return -1. The key challenge is tracking valid subarrays while ensuring they do not overlap and keeping the total length minimal.
Approach 1: Prefix Sum with HashMap + Dynamic Tracking (O(n) time, O(n) space)
Compute a running prefixSum while iterating through the array. A hash map stores the latest index where each prefix sum appears. If prefixSum - target exists in the map, you found a subarray ending at the current index with sum equal to the target. Track the length of this subarray and combine it with the shortest valid subarray that ends before it. A DP-style array stores the minimum subarray length found up to each index. This allows constant-time lookup to ensure the two subarrays do not overlap. The approach works for general arrays and leverages hash table lookups with dynamic programming state tracking.
Approach 2: Two Pointers with Sliding Window (O(n) time, O(n) space)
Because the array values are positive, you can maintain a window using two pointers. Expand the right pointer to increase the window sum and shrink from the left when the sum exceeds the target. When the window sum equals the target, record the subarray length. Similar to the previous method, keep an auxiliary array storing the shortest valid subarray length ending before each index. When a new valid window appears, combine it with the best earlier result to update the minimum total length. This approach relies on the monotonic property of positive numbers and uses the classic sliding window pattern to avoid hash lookups.
Recommended for interviews: The prefix sum + hash map method is the most commonly expected solution because it works for both positive and negative values and demonstrates control over prefix sums and state tracking. The sliding window version is cleaner and faster in practice when the array contains only positive numbers. Showing the hash map approach first proves you understand the general case; then mentioning the sliding window optimization signals strong algorithmic intuition.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Prefix Sum with HashMap + DP tracking | O(n) | O(n) | General case. Works even if negative numbers appear and demonstrates prefix sum + hash map technique. |
| Two Pointers Sliding Window | O(n) | O(n) | Best when the array contains only positive numbers and you want a simpler linear scan. |