Find Two Non-overlapping Sub-arrays Each With Target Sum solution and explanation
Google
9 more videos on this problem
LeetCode 1477. Find Two Non-overlapping Sub-arrays Each With Target SumHappy Coding · 14:44 · 4K views
花花酱 LeetCode 1477. Find Two Non-overlapping Sub-arrays Each With Target Sum - 刷题找工作 EP335Hua Hua · 14:06 · 3K views
FAANG INTERVIEW PREP - Leetcode #1477 - Find Two Non-overlapping Sub-arrays with SumLeet Terps · 13:01 · 3K views
Leetcode 1477. Find Two Non-overlapping Sub-arrays Each With Target SumDeepak Vishwakarma · 28:03 · 2K views
1477. Find Two Non-overlapping Sub-arrays Each With Target Sum | English | MediumSimple Code - 단순코드 · 15:33 · 1K views
1477. Find Two Non-overlapping Sub-arrays Each With Target Sum (python) (Leetcode Medium)Programming Live with Larry · 27:28 · 879 views
1477. Find Two Non overlapping Sub arrays Each With Target Sum - Daily Leetcode (Day 39)yeetcode · 21:35 · 482 views
Find Two Non-overlapping Sub-arrays | LeetCode 1477 | Google Interview Question | Java | StacyStacy · 2:52 · 362 views
Find Two Non-overlapping Sub-arrays Each With Target Sum | Leetcode 1477 | Part 1 | HindiCore Concepts · 11:11 · 209 views
小飞羊 LeetCode 1477 Find Two Non overlapping Sub arrays Each With Target Sum 套路得人薪C++Willy小飞羊 DJ · 5:53 · 157 views
The problem
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 <= 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.
def minSumOfLengths(arr, target):
n = len(arr)
prefix_map = {0: -1}
min_length = [float('inf')] * n
current_sum = 0
best = float('inf')
for i in range(n):
current_sum += arr[i]
if (current_sum - target) in prefix_map:
start = prefix_map[current_sum - target]
if start != -1:
min_length[i] = min(min_length[i-1], i - start)
else:
min_length[i] = min_length[i-1]
else:
min_length[i] = min_length[i-1]
prefix_map[current_sum] = i
current_sum = 0
suffix_map = {}
for i in range(n-1, -1, -1):
current_sum += arr[i]
if (current_sum - target) in suffix_map:
start = suffix_map[current_sum - target]
best = min(best, start - i + min_length[i-1])
suffix_map[current_sum] = i
return best if best != float('inf') else -1import java.util.*;
public class Solution {
public int minSumOfLengths(int[] arr, int target) {
int n = arr.length;
Map<Integer, Integer> prefixMap = new HashMap<>();
prefixMap.put(0, -1);
int[] minLength = new int[n];
Arrays.fill(minLength, Integer.MAX_VALUE);
int currentSum = 0;
int best = Integer.MAX_VALUE;
for (int i = 0; i < n; i++) {
currentSum += arr[i];
if (prefixMap.containsKey(currentSum - target)) {
int start = prefixMap.get(currentSum - target);
minLength[i] = start == -1 ? minLength[i - 1] : Math.min(minLength[i - 1], i - start);
} else {
minLength[i] = i == 0 ? Integer.MAX_VALUE : minLength[i - 1];
}
prefixMap.put(currentSum, i);
}
currentSum = 0;
Map<Integer, Integer> suffixMap = new HashMap<>();
for (int i = n - 1; i >= 0; i--) {
currentSum += arr[i];
if (suffixMap.containsKey(currentSum - target)) {
int start = suffixMap.get(currentSum - target);
best = Math.min(best, start - i + (i > 0 ? minLength[i - 1] : Integer.MAX_VALUE));
}
suffixMap.put(currentSum, i);
}
return best == Integer.MAX_VALUE ? -1 : best;
}
}function minSumOfLengths(arr, target) {
let n = arr.length;
let prefixMap = new Map();
prefixMap.set(0, -1);
let minLength = Array(n).fill(Infinity);
let currentSum = 0;
let best = Infinity;
for (let i = 0; i < n; i++) {
currentSum += arr[i];
if (prefixMap.has(currentSum - target)) {
let start = prefixMap.get(currentSum - target);
minLength[i] = start === -1 ? minLength[i - 1] : Math.min(minLength[i - 1], i - start);
} else {
minLength[i] = i > 0 ? minLength[i - 1] : Infinity;
}
prefixMap.set(currentSum, i);
}
currentSum = 0;
let suffixMap = new Map();
for (let i = n - 1; i >= 0; i--) {
currentSum += arr[i];
if (suffixMap.has(currentSum - target)) {
let start = suffixMap.get(currentSum - target);
best = Math.min(best, start - i + (i > 0 ? minLength[i - 1] : Infinity));
}
suffixMap.set(currentSum, i);
}
return best === Infinity ? -1 : best;
}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.
Time Complexity: O(n), as we iterate through the array twice.
Space Complexity: O(n), for storing prefix sums in the hashmap.
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.
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
int minSumOfLengths(vector<int>& arr, int target) {
int n = arr.size();
vector<int> minLength(n, INT_MAX);
int left = 0, right = 0, sum = 0, best = INT_MAX;
while (right < n) {
sum += arr[right];
while (sum > target) {
sum -= arr[left++];
}
if (sum == target) {
int currentLength = right - left + 1;
if (left > 0 && minLength[left - 1] != INT_MAX) {
best = min(best, minLength[left - 1] + currentLength);
}
minLength[right] = min((right > 0 ? minLength[right - 1] : INT_MAX), currentLength);
} else {
minLength[right] = right > 0 ? minLength[right - 1] : INT_MAX;
}
right++;
}
return best == INT_MAX ? -1 : best;
}
int main() {
vector<int> arr = {3,2,2,4,3};
cout << minSumOfLengths(arr, 3) << endl;
return 0;
}using System;
using System.Collections.Generic;
public class Solution {
public int MinSumOfLengths(int[] arr, int target) {
int n = arr.Length;
int[] minLength = new int[n];
Array.Fill(minLength, int.MaxValue);
int left = 0, right = 0, sum = 0, best = int.MaxValue;
while (right < n) {
sum += arr[right];
while (sum > target) {
sum -= arr[left++];
}
if (sum == target) {
int currentLength = right - left + 1;
if (left > 0 && minLength[left - 1] != int.MaxValue) {
best = Math.Min(best, minLength[left - 1] + currentLength);
}
minLength[right] = Math.Min((right > 0 ? minLength[right - 1] : int.MaxValue), currentLength);
} else {
minLength[right] = right > 0 ? minLength[right - 1] : int.MaxValue;
}
right++;
}
return best == int.MaxValue ? -1 : best;
}
public static void Main(string[] args) {
Solution sol = new Solution();
int[] arr = {3,2,2,4,3};
Console.WriteLine(sol.MinSumOfLengths(arr, 3));
}
}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.
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.
function minSumOfLengths(arr: number[], target: number): number {
const d = new Map<number, number>();
d.set(0, 0);
let s = 0;
const n = arr.length;
const f: number[] = Array(n + 1);
const inf = 1 << 30;
f[0] = inf;
let ans = inf;
for (let i = 1; i <= n; ++i) {
const v = arr[i - 1];
s += v;
f[i] = f[i - 1];
if (d.has(s - target)) {
const j = d.get(s - target)!;
f[i] = Math.min(f[i], i - j);
ans = Math.min(ans, f[j] + i - j);
}
d.set(s, i);
}
return ans > n ? -1 : ans;
}func minSumOfLengths(arr []int, target int) int {
d := map[int]int{0: 0}
const inf = 1 << 30
s, n := 0, len(arr)
f := make([]int, n+1)
f[0] = inf
ans := inf
for i, v := range arr {
i++
f[i] = f[i-1]
s += v
if j, ok := d[s-target]; ok {
f[i] = min(f[i], i-j)
ans = min(ans, f[j]+i-j)
}
d[s] = i
}
if ans > n {
return -1
}
return ans
}Complexity comparison
| 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 | – |
Complexity analysis
| 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. |
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.