Skip to main content
Talentd

Find Two Non-overlapping Sub-arrays Each With Target Sum - Solution & Explanation

MediumArrayHash TableBinary SearchDynamic Programming13 min readAsked at: Google
Practice this problem

Problem Statement

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

Approach Overview

Problem 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 1: Prefix Sum with HashMap

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.

Code

PythonJavaJavaScript

Python

Java

JavaScript

Complexity

Time Complexity: O(n), as we iterate through the array twice.
Space Complexity: O(n), for storing prefix sums in the hashmap.

Try this approach in the editor →

Approach 2: Two Pointers with Sliding Window

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.

Code

C++C#

C++

C#

Complexity

Time Complexity: O(n) due to single traversal using sliding window.
Space Complexity: O(n) for storing minimum lengths of sub-arrays.

Try this approach in the editor →

Approach 3: Hash Table + Prefix Sum + Dynamic Programming

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Prefix Sum with HashMap

Time Complexity: O(n), as we iterate through the array twice.
Space Complexity: O(n), for storing prefix sums in the hashmap.

Two Pointers with Sliding Window

Time Complexity: O(n) due to single traversal using sliding window.
Space Complexity: O(n) for storing minimum lengths of sub-arrays.

Hash Table + Prefix Sum + Dynamic Programming—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Prefix Sum with HashMap + DP trackingO(n)O(n)General case. Works even if negative numbers appear and demonstrates prefix sum + hash map technique.
Two Pointers Sliding WindowO(n)O(n)Best when the array contains only positive numbers and you want a simpler linear scan.

Video Solution

LeetCode 1477. Find Two Non-overlapping Sub-arrays Each With Target Sum • Happy Coding • 4,734 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Find Two Non-overlapping Sub-arrays Each With Target Sum easy or hard?
The problem is rated Medium because it combines multiple techniques: prefix sums, hash maps, and dynamic programming style state tracking. Identifying a single target-sum subarray is straightforward, but enforcing non-overlap and minimizing total length adds complexity. Efficient solutions require O(n) time reasoning.
Find Two Non-overlapping Sub-arrays Each With Target Sum Python/Java solution
Python and Java implementations typically use a prefix sum variable, a HashMap (or dictionary) for sum-to-index mapping, and an array tracking the best subarray length seen so far. Each iteration checks if prefixSum - target exists and updates the minimal combined length. The approach runs in O(n) time with O(n) space.
How to solve Find Two Non-overlapping Sub-arrays Each With Target Sum in O(n)?
Maintain a running prefix sum and store previously seen sums in a hash map. When prefixSum - target appears in the map, a valid subarray ending at the current index is found. Track the length of that subarray and combine it with the shortest valid subarray ending earlier using a DP array. This guarantees non-overlapping segments and keeps the total length minimal in linear time.
What is the best approach for Find Two Non-overlapping Sub-arrays Each With Target Sum?
The optimal approach uses prefix sums with a hash map and a dynamic programming array to track the shortest valid subarray ending before each index. While scanning the array, you detect target-sum subarrays in O(1) using prefixSum - target lookups. This enables combining two non-overlapping subarrays while keeping the minimum total length. The overall complexity is O(n) time and O(n) space.
Is Find Two Non-overlapping Sub-arrays Each With Target Sum asked at Google/Amazon/Meta?
Problems involving prefix sums, sliding windows, and non-overlapping subarrays appear frequently in interviews at companies like Amazon, Google, and Meta. Variants of this problem test your ability to combine prefix sum detection with dynamic programming or interval constraints. Interviewers typically expect an O(n) solution.
What data structure is used in Find Two Non-overlapping Sub-arrays Each With Target Sum?
The main data structures are a hash map for prefix sum lookups and an auxiliary array for dynamic programming that stores the shortest valid subarray length up to each index. Some solutions also use two pointers for a sliding window when the array contains only positive integers.
What is the time complexity of Find Two Non-overlapping Sub-arrays Each With Target Sum?
The optimal algorithms run in O(n) time because the array is scanned once while maintaining prefix sums or a sliding window. Hash map lookups and updates occur in constant time. Space complexity is O(n) due to the prefix map and the auxiliary array storing the minimum subarray length seen so far.

Ready to solve this problem?

Practice Find Two Non-overlapping Sub-arrays Each With Target Sum with our built-in code editor and test cases.

Practice on FleetCode
Previous

Find Subarrays With Equal Sum