1477. Find Two Non-overlapping Sub-arrays Each With Target Sum
Difficulty: Medium | Published on 2026-09-17
Since all elements in INLINECODE0 are strictly positive (INLINECODE1), running subarray sums are strictly monotonic. This allows us to locate every subarray with sum exactly INLINECODE2 in a single linear sliding window pass, while simultaneously maintaining a running prefix-minimum DP table of shortest valid lengths to pair each found subarray with the best non-overlapping candidate to its left in $O(1)$ time.
1. Problem in Very Simple Language
You are given an array of positive integers INLINECODE3 and an integer INLINECODE4.
You need to pick two separate (non-overlapping) continuous chunks (subarrays) from INLINECODE5 such that: The sum of elements in Chunk 1 is exactly equal to INLINECODE6. The sum of elements in Chunk 2 is also exactly equal to INLINECODE7. Chunk 1 and Chunk 2 do not share any indices (they cannot overlap at all).
Goal: Find two such non-overlapping chunks such that the sum of their lengths is as small as possible.
What's given: An integer array INLINECODE8 (where every number is $\ge 1$) and an integer INLINECODE9. What to find: Two non-overlapping subarrays that each sum to INLINECODE10 with minimal combined length. What to return: The minimum total length (INLINECODE11), or INLINECODE12 if it is impossible to find two valid non-overlapping subarrays.
2. Real-Life Analogy
Imagine a continuous ribbon with numbers printed in consecutive sections. You need to cut out two separate pieces of ribbon, each containing numbers that add up to a prize score of INLINECODE13. Because ribbon material costs money, your boss wants you to use as few total inches of ribbon as possible. You cannot reuse any cut section of the ribbon for both pieces. You want to scan along the ribbon once, spot every piece that totals INLINECODE14, and pair each one with the shortest valid piece found completely to its left.
3. Important Programming Concepts I Need First
Subarray vs Subsequence
A subarray is a contiguous, unbroken slice of an array: INLINECODE15. You cannot skip elements within a subarray.Monotonicity of Running Sums
Because every element in INLINECODE16 is positive (INLINECODE17), expanding the window (INLINECODE18) strictly increases the sum, and shrinking the window from the left (INLINECODE19) strictly decreases the sum. This property enables a pure two-pointer sliding window in $O(N)$ time without backtracking.Prefix Minimum Dynamic Programming (INLINECODE20)
Let INLINECODE21 store the minimum length of any valid target-sum subarray whose right endpoint ends at or before index INLINECODE22. If a valid subarray INLINECODE23 is discovered, its length is INLINECODE24. The shortest valid subarray completely to its left ends at or before index INLINECODE25, which is stored in INLINECODE26. Combining them gives a total length of INLINECODE27 in $O(1)$ time!4. Understand the Input
Take Example 1: CODEBLOCK0
Target is INLINECODE28. Subarrays that sum to 3: INLINECODE29 at index INLINECODE30 (length 1) INLINECODE31 at index INLINECODE32 (length 1) Indices INLINECODE33 and INLINECODE34 do not overlap. Combined length = $1 + 1 = 2$.
Take Example 2: CODEBLOCK1
Target is INLINECODE35. Subarrays that sum to 7: INLINECODE36 at index INLINECODE37 (length 1) INLINECODE38 at indices INLINECODE39 (length 2) INLINECODE40 at index INLINECODE41 (length 1) Pairs of non-overlapping subarrays: Pair 1: INLINECODE42 at index 0 and INLINECODE43 at [1, 2] $\rightarrow$ length = $1 + 2 = 3$. Pair 2: INLINECODE44 at index 0 and INLINECODE45 at index 3 $\rightarrow$ length = $1 + 1 = 2$. Pair 3: INLINECODE46 at [1, 2] and INLINECODE47 at index 3 $\rightarrow$ length = $2 + 1 = 3$. The minimum combined length across all valid pairs is 2.
5. Understand the Output
Return an integer representing the smallest combined length INLINECODE48. If fewer than 2 non-overlapping target-sum subarrays exist, return INLINECODE49.
6. Solve the Example Manually
Let's manually walk through Example 2: INLINECODE50.
CODEBLOCK2
1. At INLINECODE51 (INLINECODE52): Window: INLINECODE53, INLINECODE54. Length INLINECODE55. Left partner needed before index INLINECODE56. None exists yet. Best subarray up to index 0: INLINECODE57.
2. At INLINECODE58 (INLINECODE59): Window: INLINECODE60, INLINECODE61. Shrink left: INLINECODE62, INLINECODE63. No valid target sum ending at index 1. Best subarray up to index 1: INLINECODE64.
3. At INLINECODE65 (INLINECODE66): Window: INLINECODE67, INLINECODE68. Length INLINECODE69 (from index 1 to 2). Left partner needed before index INLINECODE70. Best left length = INLINECODE71. Total pair length = INLINECODE72. Candidate answer = 3. Best subarray up to index 2: INLINECODE73.
4. At INLINECODE74 (INLINECODE75): Window: INLINECODE76, INLINECODE77. Shrink left: INLINECODE78, INLINECODE79. INLINECODE80, INLINECODE81. Length INLINECODE82 (at index 3). Left partner needed before index INLINECODE83. Best left length = INLINECODE84. Total pair length = INLINECODE85. Best total answer = INLINECODE86. Best subarray up to index 3: INLINECODE87.
Final Answer: 2 ✔️
7. Think Like a Programmer
What do I know? All elements are positive $(\ge 1)$. Any subarray summing to INLINECODE88 has a specific start INLINECODE89 and end INLINECODE90. What is the challenge? We need two non-overlapping subarrays. If we find a subarray ending at INLINECODE91, what is the best subarray that ends before INLINECODE92? Why naive searching fails: If there are $K$ valid subarrays, checking all pairs takes $O(K^2)$. In the worst case, $K = O(N)$, leading to an $O(N^2)$ time limit exceeded (TLE). The DP optimization: By storing the minimum length of any valid subarray seen up to index $i$ in a 1D array INLINECODE93, looking up the best non-overlapping left partner takes exactly $O(1)$ time!
8. Start With the Brute Force Solution
Brute force idea: 1. Find all pairs of INLINECODE94 where $\sum \text{arr}[\text{start}..\text{end}] = \text{target}$. 2. Compare every pair of intervals $(I1, I2)$ that do not overlap: $\text{end}1 < \text{start}2$. 3. Track the minimum sum of lengths $\text{len}(I1) + \text{len}(I2)$.
CODEBLOCK3
Time Complexity: $O(N^2)$ to find intervals and $O(M^2)$ to compare pairs. With $N = 10^5$, this will exceed the 2-second time limit. Space Complexity: $O(M)$ to store intervals.
9. Explain the Brute Force Code Line by Line
INLINECODE95 — collects all intervals that sum to INLINECODE96. Nested loops INLINECODE97 and INLINECODE98 compute subarray sums; when INLINECODE99, records INLINECODE100. Second nested loop checks all pairs of intervals for non-overlap condition (INLINECODE101 or INLINECODE102). Returns the minimum combined length found or INLINECODE103.
10. Why Is Brute Force Inefficient?
Finding intervals and comparing all combinations pairwise performs redundant comparisons. When we consider a valid subarray ending at INLINECODE104, we do not need to check every previous valid subarray individually. We only care about the single smallest length among all previous subarrays ending at or before INLINECODE105.
11. Find the Better Approach
"Can we maintain a running prefix minimum of valid subarray lengths while scanning with a sliding window?"
Yes! 1. Maintain a two-pointer sliding window INLINECODE106 with running sum INLINECODE107. 2. Array INLINECODE108 tracks $\min \text{length}$ of any valid target-sum subarray ending at index $\le i$. 3. When INLINECODE109 at window INLINECODE110: Current window length is INLINECODE111. If INLINECODE112 and INLINECODE113, a valid non-overlapping pair exists with combined length INLINECODE114. Update global answer: INLINECODE115. Update running prefix minimum: INLINECODE116. 4. If INLINECODE117: INLINECODE118.
12. ⭐ Key Insight
Before the insight
Checking all pairs of non-overlapping intervals requires $O(N^2)$ combinations.The insight
1. Because all values in INLINECODE119 are positive, a simple sliding window discovers every valid subarray in $O(N)$ time. 2. A 1D prefix-minimum DP array (INLINECODE120) allows $O(1)$ query of the shortest non-overlapping subarray to the left. 3. Evaluating the pair before recording the current window into INLINECODE121 guarantees the two chosen subarrays never overlap or reuse the same segment.After the insight
The solution runs in a single clean $O(N)$ pass with $O(N)$ auxiliary space.13. Dry Run the Optimized Solution
Let's trace INLINECODE122, INLINECODE123, INLINECODE124.
| INLINECODE125 | INLINECODE126 | INLINECODE127 (after shrink) | INLINECODE128 | INLINECODE129? | INLINECODE130 | Left Partner (INLINECODE131) | Candidate Pair | INLINECODE132 | Best INLINECODE133 |
|---|---|---|---|---|---|---|---|---|---|
| 0 | 7 | 7 | 0 | Yes | 1 | None (INLINECODE134) | - | 1 | INF |
| 1 | 3 | 3 | 1 | No | - | - | - | 1 | INF |
| 2 | 4 | 7 | 1 | Yes | 2 | INLINECODE135 | $1 + 2 = 3$ | $\min(1, 2) = 1$ | 3 |
| 3 | 7 | 7 | 3 | Yes | 1 | INLINECODE136 | $1 + 1 = 2$ | $\min(1, 1) = 1$ | 2 |
14. Optimized Solution Code
Java
CODEBLOCK4Python3
CODEBLOCK5JavaScript
CODEBLOCK6C++
CODEBLOCK715. Explain the Optimized Code Line by Line
INLINECODE138 — sentinel value representing no valid subarray found yet, halved to prevent integer overflow during INLINECODE139. INLINECODE140 — initializes two pointers and the global minimum answer. INLINECODE141 — expands the sliding window by including the element at INLINECODE142. INLINECODE143 — shrinks window until INLINECODE144. INLINECODE145 — carries forward the shortest valid subarray length found up to index INLINECODE146. INLINECODE147 — checks if the current window is a match. INLINECODE148 — calculates the length of the current matching subarray. INLINECODE149 — if a non-overlapping valid subarray exists to the left, update INLINECODE150. INLINECODE151 — updates the minimum length for the prefix ending at INLINECODE152. INLINECODE153 — stores the prefix minimum into INLINECODE154. INLINECODE155 — returns the answer if at least two non-overlapping subarrays were found, otherwise INLINECODE156.
16. Test With Multiple Examples
Example 1: INLINECODE157
Subarrays with sum 3: INLINECODE158 at index 0 (len 1) and INLINECODE159 at index 4 (len 1). Output: INLINECODE160 ✔️Example 2: INLINECODE161
Subarrays: INLINECODE162 at 0 (len 1), INLINECODE163 at 1..2 (len 2), INLINECODE164 at 3 (len 1). Best pair: index 0 and index 3 $\rightarrow$ combined length = $1 + 1 = 2$. Output: INLINECODE165 ✔️Example 3: INLINECODE166
Subarrays: INLINECODE167 is not contiguous; valid contiguous subarrays are INLINECODE168 at index 3 (len 1) and INLINECODE169 (sum 9 > 6). Output: INLINECODE170 (only 1 valid subarray exists) ✔️17. Edge Cases
No valid subarray exists: If no subarray sums to INLINECODE171, returns INLINECODE172. Only one valid subarray exists: If only 1 subarray sums to INLINECODE173, no non-overlapping pair can be formed $\rightarrow$ returns INLINECODE174. Multiple identical target elements: E.g., INLINECODE175 $\rightarrow$ pairs INLINECODE176 and INLINECODE177 to return INLINECODE178. Overlapping matches: E.g., INLINECODE179 $\rightarrow$ ignores overlapping matches and strictly pairs non-overlapping segments. Large constraints ($N = 10^5$): Linear $O(N)$ execution completes in $< 15$ ms.18. Time Complexity
Sliding Window: Each index is visited at most twice (once by INLINECODE180, once by INLINECODE181), taking $O(N)$ operations. DP Updates: Each step performs $O(1)$ constant-time arithmetic and lookups. Total Time Complexity: $\mathcal{O}(N)$, optimal for $N = 10^5$.
19. Space Complexity
DP Array: Requires an array of size $N$ to store prefix minimums. Total Space Complexity: $\mathcal{O}(N)$.
20. Common Mistakes Beginners Make
❌ "Updating INLINECODE182 before pairing with INLINECODE183." If you update the DP array with the current window before evaluating candidate pairs, a subarray could accidentally pair with a piece of itself or an overlapping segment. ❌ "Using Integer.MAXVALUE directly without halving." Evaluating INLINECODE184 causes integer overflow into negative values, corrupting INLINECODE185. Always use a safe sentinel like INLINECODE186 or INLINECODE187. ❌ "Assuming negative numbers can be present." The problem constraints state $arr[i] \ge 1$. If negative numbers were allowed, sliding window would fail and a prefix sum hash table with a segment tree or monotonic stack would be needed.
21. How to Recognize This Pattern in Other Problems
Look for these key identifiers: 1. "Find two non-overlapping sub-arrays..." 2. "Minimize or maximize the sum of their metrics (lengths, sums, profits)..." 3. Array with non-negative / monotonic properties.
Whenever you see "find 2 non-overlapping subarrays," use the Left-to-Right Prefix DP + Current Subarray pattern: Compute the best candidate ending $\le i$ from the left. Scan the second subarray and look up the best non-overlapping answer from the prefix DP in $O(1)$.
22. Interview Thinking
CODEBLOCK8
23. Quiz & Practice Challenge
1. Question 1: Why does sliding window work here instead of requiring a hash map for prefix sums? Answer: Because all elements are positive ($arr[i] \ge 1$), which ensures subarray sums are strictly monotonic when expanding and shrinking. 2. Question 2: What would be the time complexity if we used a Hash Map to find all $K$ valid intervals and then compared all pairs? Answer: $O(K^2)$, which degrades to $O(N^2)$ in the worst case (e.g., all 1s). 3. Question 3: Can this pattern be extended to find $k$ non-overlapping subarrays? Answer: Yes, using a 2D DP table INLINECODE188 where INLINECODE189_ ranges from $1$ to $k$.