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.
This approach involves calculating the prefix sum to quickly determine the sum of sub-arrays. We use a HashMap to store the smallest sub-array length that achieves the target sum from the start up to each index. As we iterate through the array, we use this information to find two non-overlapping sub-arrays with a sum equal to the target and calculate the minimal sum of their lengths.
We maintain a prefix sum and use a hashmap to track indices where certain prefix sums occur. By iterating over the array twice, once from the left and once from the right, we ensure non-overlapping conditions and track the minimum sub-array lengths effectively.
Python
Java
JavaScript
Time Complexity: O(n), as we iterate through the array twice.
Space Complexity: O(n), for storing prefix sums in the hashmap.
The method involves two-pointers to manage sliding windows over the array. By keeping track of different window positions with two sets of pointers, we identify potential sub-arrays satisfying the sum condition and ensure they don't overlap.
Using a sliding window mechanism with two pointers, this C++ solution finds minimal length sub-arrays for the target sum. The use of minLength ensures non-overlapping sub-arrays are accounted without overlap.
Time Complexity: O(n) due to single traversal using sliding window.
Space Complexity: O(n) for storing minimum lengths of sub-arrays.
We can use a hash table d to record the most recent position where each prefix sum appears, with the initial value d[0]=0.
Define f[i] as the minimum length of a subarray with sum equal to target among the first i elements. Initially, f[0]=infty.
Iterate through the array arr. For the current position i, calculate the prefix sum s. If s - target exists in the hash table, let j = d[s - target], then f[i] = min(f[i], i - j), and the answer is ans = min(ans, f[j] + i - j). Continue to the next position.
Finally, if the answer is greater than the array length, return -1; otherwise, return the answer.
The complexity is O(n), and the space complexity is O(n), where n is the length of the array.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Prefix Sum with HashMap | Time Complexity: O(n), as we iterate through the array twice. |
| Two Pointers with Sliding Window | Time Complexity: O(n) due to single traversal using sliding window. |
| Hash Table + Prefix Sum + Dynamic Programming | — |
| 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. |
LeetCode 1477. Find Two Non-overlapping Sub-arrays Each With Target Sum • Happy Coding • 4,664 views views
Watch 9 more video solutions →Practice Find Two Non-overlapping Sub-arrays Each With Target Sum with our built-in code editor and test cases.
Practice on FleetCode