1477. Find Two Non-overlapping Sub-arrays Each With Target Sum
Problem Description
The problem requires finding two non-overlapping sub-arrays within a given array of integers, arr
, where each sub-array sums up to a specific value, target
. To qualify, neither of the sub-arrays should share any elements with the other, effectively meaning they cannot overlap. The goal is to find such pair of sub-arrays where the combined length of both sub-arrays is as small as possible. If it's impossible to find such pair of sub-arrays, the function should return -1
.
Intuition
The solution to this problem involves dynamic programming and the use of a hashmap to track the prefix sums.
-
The intuition behind the dynamic programming approach is that at any point in the array, we want to know the length of the smallest sub-array ending at that point which sums to
target
. This can help us efficiently update the answer when we find the next sub-array that sums totarget
. -
To efficiently find if a sub-array sums to
target
, we can use a hashmap to store the sum of all elements up to the current index (s
), as the key, with the value being the index itself. Ifs - target
is in the hashmap, it means there is a valid sub-array ending at the current index which sums totarget
. -
While iterating through the array, we keep updating our hashmap with the current sum and index, and we also keep track of the smallest sub-array found so far that sums to
target
using an arrayf
. -
Whenever a new sub-array is found (checking if
s - target
exists in the hashmap), we calculate the minimum length of a sub-array that sums totarget
that ends at our current index. Simultaneously, we try to update the global answer, which is the sum of lengths of two such sub-arrays.
The key realization is that we do not need to store the actual sub-arrays. Instead, storing their lengths and endpoints suffices to solve the problem. By maintaining a running minimum length sub-array and utilizing the hashmap to efficiently query the existence of a previous sub-array sum, we can determine the optimal pair of sub-arrays that fulfill the conditions.
Learn more about Binary Search, Dynamic Programming and Sliding Window patterns.
Solution Approach
The implementation utilizes a hashmap and a dynamic programming (DP) table. Here is a step-by-step breakdown:
-
Hashmap for Prefix Sums:
- A hashmap
d
is used to store the sum of all elements up to the current index as keys (s
presents the current sum) and their corresponding indices as values. This helps quickly check if there is a sub-array ending at the current index that sums up totarget
.
- A hashmap
-
Initializing Variables:
s
is the prefix sum initialized to 0.n
is the total number of elements in the arrayarr
.f
is an array of sizen+1
initialized toinf
(infinity).f[i]
will hold the length of the smallest sub-array ending before or at indexi
, which has a sum oftarget
.ans
is initialized toinf
and will be used to store the minimum sum of the lengths of the two non-overlapping sub-arrays found so far.
-
Iterating Through the Array:
- Using a for loop, we iterate through the array starting from index 1 (since
f
is 1-indexed to simplify calculations). - We update the prefix sum
s
by adding the current elementv
.
- Using a for loop, we iterate through the array starting from index 1 (since
-
Dynamic Programming Table Update:
- At each index
i
, the current value off[i]
is set tof[i - 1]
, ensuring that we carry forward the length of the smallest sub-array found so far up to the previous index.
- At each index
-
Finding and Updating Sub-arrays:
- At each step of the iteration, we check if
s - target
is in the hashmapd
. - If it is, that means we have encountered a sub-array, ending at the current index, which sums up to
target
. - We retrieve this sub-arrayās starting index
j
from the hashmap, and we calculate its lengthi - j
. - Then we update
f[i]
as the minimum of the current value and the length of this new sub-array, which reflects the smallest sub-array summing totarget
up to indexi
.
- At each step of the iteration, we check if
-
Updating the Answer:
- While a new valid sub-array is found, we calculate the sum of its length with the smallest length of a sub-array found before it, i.e.,
f[j] + i - j
. - If this sum is smaller than our current answer, we update the answer
ans
.
- While a new valid sub-array is found, we calculate the sum of its length with the smallest length of a sub-array found before it, i.e.,
-
Returning the Answer:
- After iterating through the entire array, it is possible that no such pair of sub-arrays was found. We check this by comparing
ans
withn
. - If
ans
is stillinf
or greater thann
, it means no two non-overlapping sub-arrays with the sumtarget
were found, and we return-1
. - Otherwise, we return
ans
, which is the minimum sum of the lengths of the required two sub-arrays.
- After iterating through the entire array, it is possible that no such pair of sub-arrays was found. We check this by comparing
By the end of the loop, we either find the minimum sum of lengths of two non-overlapping sub-arrays that sum up to target
, or determine that itās not possible to find such sub-arrays and return -1
.
The use of the DP approach with a hashmap allows the algorithm to run efficiently by preventing repeated scanning of the array to check for sub-arrays that sum to target
.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach with a small example. Consider the array arr = [1, 2, 1, 2, 1, 2, 1]
with target = 3
.
-
Hashmap for Prefix Sums: We will use a hashmap
d
to keep track of the prefix sums. Initially,d
is empty. -
Initializing Variables:
s
starts at 0.n
is7
, the total number of elements inarr
.f
is an array[inf, inf, inf, inf, inf, inf, inf, inf]
(1-indexed for a total ofn+1
entries).ans
is initialized toinf
.
-
Iterating Through the Array: We iterate
i
from 1 to 7, and for each elementv
inarr
, we updates
. -
Dynamic Programming Table Update: At each index,
f[i]
is updated to be the minimum length of a valid sub-array up to that point. -
Finding and Updating Sub-arrays:
- For each
v
, we calculates
and check ifs - target
exists ind
. - If it does, we find the length of the current sub-array and update
f[i]
with the minimum.
- For each
-
Updating the Answer:
- Each time we find a valid sub-array, we calculate if it can contribute to a smaller
ans
.
- Each time we find a valid sub-array, we calculate if it can contribute to a smaller
-
Returning the Answer: At the end, we return
ans
or-1
if not found.
Now, let's walk through with our array:
- Initial step:
d = {0: 0}
to account for starting from a sum of0
at index0
. i = 1
,arr[1] = 1
.s = 1
.f = [inf, inf, inf, inf, inf, inf, inf, inf]
,ans = inf
.d = {0: 0, 1: 1}
.i = 2
,arr[2] = 2
,s = 3
. We sees - target = 0
ind
. Sub-array[1, 2]
has sum3
. Updatef[2] = min(inf, 2 - 0) = 2
.d = {0: 0, 1: 1, 3: 2}
.i = 3
,arr[3] = 1
.s = 4
. No change sinces - target = 1
is not a prefix sum we've seen that ended at an index beforei
.d = {0: 0, 1: 1, 3: 2, 4: 3}
.i = 4
,arr[4] = 2
.s = 6
. We finds-target = 3
ind
. The sub-array[1, 2]
happens again. Updatef[4] = min(inf, 4 - 2) = 2
.ans = min(inf, f[2] + 2) = min(inf, 2 + 2) = 4
.d = {0: 0, 1: 1, 3: 2, 4: 3, 6: 4}
.i = 5
,arr[5] = 1
.s = 7
. We finds-target = 4
ind
. Updatef[5] = min(inf, 5 - 3) = 2
. Ans does not update becausef[3]
wasinf
.d = {0: 0, 1: 1, 3: 2, 4: 3, 6: 4, 7: 5}
.i = 6
,arr[6] = 2
.s = 9
. We finds-target = 6
ind
. Updatef[6] = min(inf, 6 - 4) = 2
.ans = min(4, f[4] + 2) = min(4, 2 + 2) = 4
.d = {0: 0, 1: 1, 3: 2, 4: 3, 6: 4, 7: 5, 9: 6}
.i = 7
,arr[7] = 1
.s = 10
. We finds-target = 7
ind
. Updatef[7] = min(inf, 7 - 5) = 2
.ans = min(4, f[5] + 2) = min(4, 2 + 2) = 4
.d = {0: 0, 1: 1, 3: 2, 4: 3, 6: 4, 7: 5, 9: 6, 10: 7}
.
After completing the iteration, we have ans = 4
, which corresponds to two non-overlapping sub-arrays [1, 2]
and [1, 2]
, both sum up to 3
, with a combined minimum length of 4
. Hence, the function would return 4
.
Solution Implementation
1class Solution:
2 def minSumOfLengths(self, arr: List[int], target: int) -> int:
3 # Create a dictionary to remember sum of all elements till index i (0-indexed)
4 sum_to_index = {0: -1} # Adjusted for 0-index, starting with sum 0 at index -1
5 current_sum = 0 # Current sum of elements
6 final_result = float('inf') # Initialize the final_result with infinity
7
8 # Minimum length subarray ending at i that sums to target
9 min_len_subarray = [float('inf')] * len(arr)
10
11 for i, value in enumerate(arr):
12 current_sum += value # Update the current_sum with the current value
13
14 # Update the min_len_subarray for the current position
15 if i > 0:
16 min_len_subarray[i] = min_len_subarray[i - 1]
17
18 # If the current_sum minus target sum is in sum_to_index...
19 if current_sum - target in sum_to_index:
20 # Get the start index of subarray ending at current index i
21 start_index = sum_to_index[current_sum - target]
22 # Calculate the length of this subarray
23 current_len = i - start_index
24 # Update the minimum length subarray for the current position
25 min_len_subarray[i] = min(min_len_subarray[i], current_len)
26 # If this is not the first element, consider previous subarrays and update final_result
27 if start_index >= 0:
28 final_result = min(final_result, min_len_subarray[start_index] + current_len)
29
30 # Update the sum_to_index with the current_sum at current index i
31 sum_to_index[current_sum] = i
32
33 # If final_result was updated and is not infinity, return it, else return -1
34 return final_result if final_result != float('inf') else -1
35
1class Solution {
2 public int minSumOfLengths(int[] arr, int target) {
3 // Hash map to store the cumulative sum up to the current index with the index itself
4 Map<Integer, Integer> cumSumToIndex = new HashMap<>();
5 cumSumToIndex.put(0, 0); // Initialization with sum 0 at index 0
6
7 int n = arr.length; // Length of the array
8 int[] minLengths = new int[n + 1]; // Array to store the minimum subarray length ending at i that sums up to target
9 final int infinity = 1 << 30; // A very large number treated as infinity
10 minLengths[0] = infinity; // Initialize with infinity since there's no subarray ending at index 0
11
12 int currentSum = 0; // Sum of the current subarray
13 int answer = infinity; // Initialize the answer with a large number representing infinity
14
15 // Loop through the array to find minimum subarrays
16 for (int i = 1; i <= n; ++i) {
17 int value = arr[i - 1]; // Value at current index in the array
18 currentSum += value; // Update the current sum
19
20 // Copy the minimum subarray length found so far to current position
21 minLengths[i] = minLengths[i - 1];
22
23 // If the (currentSum - target) is found before, update the minimum length and answer
24 if (cumSumToIndex.containsKey(currentSum - target)) {
25 int j = cumSumToIndex.get(currentSum - target); // Previous index where the cumulative sum was currentSum - target
26 minLengths[i] = Math.min(minLengths[i], i - j); // Update the minimum length for current index
27 answer = Math.min(answer, minLengths[j] + i - j); // Calculate the combined length and update the answer
28 }
29
30 // Store the current cumulative sum and corresponding index
31 cumSumToIndex.put(currentSum, i);
32 }
33
34 // If the answer is still infinity, no such subarrays are found; return -1. Else, return the found answer
35 return answer > n ? -1 : answer;
36 }
37}
38
1class Solution {
2public:
3 // This function finds two non-overlapping subarrays which sum to the target and returns
4 // the minimum sum of their lengths or -1 if there are no such subarrays.
5 int minSumOfLengths(vector<int>& arr, int target) {
6 unordered_map<int, int> prefixSumToIndex;
7 prefixSumToIndex[0] = -1; // Initialization with a base case
8
9 int prefixSum = 0, arraySize = arr.size();
10
11 // Initialize the array to store the minimum length of a subarray ending at each index i that sums to target.
12 vector<int> minLenToEndAt(arraySize + 1, INT_MAX);
13 minLenToEndAt[0] = INT_MAX; // No subarray ends before the array starts.
14
15 int minTotalLen = INT_MAX; // This will store the result.
16
17 for (int i = 0; i < arraySize; ++i) {
18 prefixSum += arr[i]; // Add the current element to the prefix sum.
19
20 // Update the minimum length for a subarray ending at the current index.
21 if (i > 0) {
22 minLenToEndAt[i + 1] = minLenToEndAt[i];
23 }
24
25 // If the prefix sum needed to achieve the target exists...
26 if (prefixSumToIndex.count(prefixSum - target)) {
27 int startIndex = prefixSumToIndex[prefixSum - target];
28 // Update the minimum length for this index.
29 minLenToEndAt[i + 1] = min(minLenToEndAt[i + 1], i - startIndex);
30
31 // If the previous subarray (ending at startIndex) is valid...
32 if (minLenToEndAt[startIndex + 1] < INT_MAX) {
33 // Update the minimum total length.
34 minTotalLen = min(minTotalLen, minLenToEndAt[startIndex + 1] + i - startIndex);
35 }
36 }
37
38 // Update or add the current prefix sum and its ending index to the map.
39 prefixSumToIndex[prefixSum] = i;
40 }
41
42 // If minTotalLen is not updated, return -1 to indicate no such subarrays exist.
43 return minTotalLen == INT_MAX ? -1 : minTotalLen;
44 }
45};
46
1// Initialize a helper function to find the minimum of two numbers
2function min(a: number, b: number): number {
3 return a < b ? a : b;
4}
5
6// This function finds two non-overlapping subarrays which sum to the target
7// and returns the minimum sum of their lengths, or -1 if there are no such
8// subarrays.
9function minSumOfLengths(arr: number[], target: number): number {
10 const prefixSumToIndex: Map<number, number> = new Map();
11 prefixSumToIndex.set(0, -1); // Initialization with a base case
12
13 let prefixSum: number = 0;
14 const arraySize: number = arr.length;
15
16 // Initialize the array to store the minimum length of a subarray ending at each index i that sums to target.
17 const minLenToEndAt: number[] = new Array(arraySize + 1).fill(Number.MAX_SAFE_INTEGER);
18 minLenToEndAt[0] = Number.MAX_SAFE_INTEGER; // No subarray ends before the array starts.
19
20 let minTotalLen: number = Number.MAX_SAFE_INTEGER; // This will store the result.
21
22 for (let i = 0; i < arraySize; ++i) {
23 prefixSum += arr[i]; // Add the current element to the prefix sum.
24
25 // Update the minimum length for a subarray ending at the current index.
26 if (i > 0) {
27 minLenToEndAt[i + 1] = minLenToEndAt[i];
28 }
29
30 // If the prefix sum needed to achieve the target exists...
31 const neededSum = prefixSum - target;
32 if (prefixSumToIndex.has(neededSum)) {
33 const startIndex = prefixSumToIndex.get(neededSum);
34 // Update the minimum length for this index.
35 minLenToEndAt[i + 1] = min(minLenToEndAt[i + 1], i - startIndex!);
36
37 // If the previous subarray (ending at startIndex) is valid...
38 if (minLenToEndAt[startIndex! + 1] < Number.MAX_SAFE_INTEGER) {
39 // Update the minimum total length.
40 minTotalLen = min(minTotalLen, minLenToEndAt[startIndex! + 1] + i - startIndex!);
41 }
42 }
43
44 // Update or add the current prefix sum and its ending index to the map.
45 prefixSumToIndex.set(prefixSum, i);
46 }
47
48 // If minTotalLen is not updated, return -1 to indicate no such subarrays exist.
49 return minTotalLen === Number.MAX_SAFE_INTEGER ? -1 : minTotalLen;
50}
51
Time and Space Complexity
Time Complexity
The time complexity of the code is O(N)
, where N
is the number of elements in the array arr
. This is because the code iterates through the array once, with constant-time operations performed for each element (such as updating a dictionary, arithmetic operations, and comparison operations).
More specifically:
- We have a single
for
loop iterating overarr
, so we visit each element ofarr
once. - For each element in the
for
loop, we are performing a dictionary lookup (or insertion) for operationd[s] = i
andd[s - target]
which is typicallyO(1)
on average for a hash table. - Assignments and comparisons like
f[i] = f[i - 1]
andans = min(ans, f[j] + i - j)
areO(1)
operations. Therefore, combining these constant-time operations within a single loop overn
elements, the overall time complexity is linear, represented byO(N)
.
Space Complexity
The space complexity of the code is O(N)
as well. This can be attributed to two data structures that scale with the input size:
- The dictionary
d
which, in the worst case, could contain an entry for each prefix sum. - The list
f
which containsn + 1
elements (as it keeps a record of the minimum length of a subarray for every index up ton
).
Since both d
and f
only grow linearly with the input array's size, the space complexity is linear, represented by O(N)
.
Learn more about how to find time and space complexity quickly using problem constraints.
The three-steps of Depth First Search are:
- Identify states;
- Draw the state-space tree;
- DFS on the state-space tree.
Recommended Readings
Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
https algomonster s3 us east 2 amazonaws com cover_photos stack svg Sliding Window Maximum Monotonic Stack We have an array and a sliding window defined by a start index and an end index The sliding window moves from left of the array to right There are always k elements in
Want a Structured Path to Master System Design Too? Donāt Miss This!