Start by scanning the array while tracking cumulative sums with a hash map to identify sub-arrays that match the target. Use two auxiliary arrays to store the minimal lengths from the left and right to ensure non-overlapping sub-arrays. Combine these results to compute the minimal total length or return -1 if no valid pair exists, balancing efficiency and correctness.
Problem Statement
Given an integer array arr and an integer target, find two non-overlapping sub-arrays where each sub-array sums exactly to target. Your goal is to minimize the sum of their lengths.
Return the minimal sum of lengths of these two sub-arrays, or -1 if it is impossible to find such two sub-arrays. Consider scenarios where multiple sub-arrays exist but only certain pairs yield the minimal combined length.
Examples
Example 1
Input: arr = [3,2,2,4,3], target = 3
Output: 2
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
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
We have only one sub-array of sum = 6.
Constraints
- 1 <= arr.length <= 105
- 1 <= arr[i] <= 1000
- 1 <= target <= 108
Solution Approach
Prefix Scan with Hash Map
Maintain a running prefix sum while iterating over the array. Store each prefix sum in a hash map pointing to its index. Whenever the difference between current prefix sum and target exists in the map, record the sub-array length.
Build Minimal Left and Right Arrays
Create two arrays: prefix[i] stores the minimum sub-array length ending before index i, suffix[i] stores the minimum sub-array length starting at or after index i. This helps quickly check non-overlapping pairs.
Combine Results for Minimal Total Length
Iterate over all split points to combine prefix and suffix lengths. Track the minimal sum of two non-overlapping sub-arrays, ensuring indices do not overlap. Return -1 if no valid combination is found.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | Depends on the final approach |
| Space | Depends on the final approach |
Time complexity is O(n) because each element is scanned once and hash map lookups are O(1). Space complexity is O(n) for the prefix and suffix arrays plus the hash map.
What Interviewers Usually Probe
- Check for multiple sub-arrays with the same sum and ensure non-overlapping selection.
- Expect discussion on using prefix sums with hash maps to quickly identify valid sub-arrays.
- Watch for edge cases where no two valid sub-arrays exist, requiring a -1 return.
Common Pitfalls or Variants
Common pitfalls
- Overlapping sub-arrays are mistakenly counted; always verify index boundaries.
- Not updating the minimal length in prefix or suffix arrays, leading to incorrect total length.
- Ignoring single sub-array cases where a second sub-array does not exist.
Follow-up variants
- Find k non-overlapping sub-arrays with the same target sum and minimize total length.
- Return the maximal total length of two non-overlapping sub-arrays with target sum.
- Handle arrays with negative integers, requiring careful prefix sum handling.
How GhostInterview Helps
- Automatically computes prefix sums and minimal sub-array lengths, reducing manual tracking errors.
- Highlights non-overlapping sub-array combinations to ensure correct minimal total length.
- Identifies edge cases and provides step-by-step debugging for array scanning plus hash lookup patterns.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
FAQ
What is the main strategy to solve Find Two Non-overlapping Sub-arrays Each With Target Sum?
Use a prefix sum hash map to locate sub-arrays efficiently, then combine minimal left and right lengths to find non-overlapping pairs.
How do prefix and suffix arrays help in this problem?
Prefix and suffix arrays store minimal lengths of sub-arrays from the left and right, allowing quick combination checks without overlap.
Can the array contain negative numbers?
Yes, but prefix sum tracking must account for decreasing sums, which may require extra care in hash map updates.
What should be returned if only one valid sub-array exists?
Return -1 because the problem requires exactly two non-overlapping sub-arrays.
Is this problem solved using sliding window?
Sliding window works only for positive integers; for mixed or general cases, hash map prefix sums ensure correctness.
Need direct help with Find Two Non-overlapping Sub-arrays Each With Target Sum instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Find Two Non-overlapping Sub-arrays Each With Target Sum from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Find the minimum number of operations to reduce a value x to zero by removing elements from an array.
Open problem page#1027 Longest Arithmetic SubsequenceFind the length of the longest arithmetic subsequence in a given integer array using scanning and hash-based lookup.
Open problem page#2008 Maximum Earnings From TaxiMaximize earnings by optimizing taxi ride selection and tips using array scanning, hash lookups, and sorting.
Open problem page