Find Two Non-overlapping Sub-arrays Each With Target Sum
MediumAsked by:
18 views
Topics:
ArraysSliding Windows
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
Solution
Clarifying Questions
When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:
- What is the expected return value if no two non-overlapping sub-arrays sum to the target?
- Can the input array contain negative numbers, zeros, or non-integer values?
- What are the possible size ranges for the input array, and are there any constraints on the magnitude of the target value?
- If multiple pairs of sub-arrays satisfy the conditions, which pair (or metric of the pair) should I return, e.g., minimize the sum of the lengths, minimize the length of the shorter sub-array, etc.?
- Is the sub-array required to be contiguous in the original array?
Brute Force Solution
Approach
The brute force method is like trying every single possibility until you find the correct one. In this problem, it means checking every combination of two sections within the larger list to see if they both add up to the target sum.
Here's how the algorithm would work step-by-step:
- First, consider all possible starting points and ending points for the very first section.
- For each of these first sections, check if the numbers within it add up to the target sum.
- If the first section adds up to the target sum, we then look at the numbers that are *not* in that section, which forms the rest of our larger list.
- Now, within that 'rest of the list', we repeat the same process: consider all possible starting and ending points for a *second* section.
- Again, for each of those possible second sections, we check if it adds up to the target sum.
- If we find *both* a first section and a second section (that don't overlap) that each add up to the target sum, we save the lengths of those two sections.
- After trying every possible first section and second section, we look at all the saved pairs of lengths, and we pick the pair that has the smallest total length.
Code Implementation
def find_two_non_overlapping_sub_arrays_each_with_target_sum_brute_force(numbers, target): minimum_total_length = float('inf')
list_length = len(numbers)
for first_start_index in range(list_length):
for first_end_index in range(first_start_index, list_length):
first_sub_array = numbers[first_start_index:first_end_index+1]
if sum(first_sub_array) == target:
# Now find the second sub array in the remaining part of the list.
for second_start_index in range(list_length):
for second_end_index in range(second_start_index, list_length):
second_sub_array = numbers[second_start_index:second_end_index+1]
# Check if the sub arrays are non-overlapping and the second sums to the target
if sum(second_sub_array) == target:
if not (first_end_index < second_start_index or second_end_index < first_start_index):
continue
first_sub_array_length = len(first_sub_array)
second_sub_array_length = len(second_sub_array)
total_length = first_sub_array_length + second_sub_array_length
# We now compare total lengths
minimum_total_length = min(minimum_total_length, total_length)
if minimum_total_length == float('inf'):
return -1
else:
return minimum_total_lengthBig(O) Analysis
Time Complexity
O(n^4) – The algorithm iterates through all possible subarrays to find the first subarray with the target sum. This involves two nested loops, each up to n, resulting in O(n^2) complexity. For each such first subarray found, the algorithm searches for a second non-overlapping subarray with the target sum, again using two nested loops over the remaining portion of the array (which is still bounded by n), resulting in another O(n^2) complexity. Since these two operations are nested, the overall time complexity is O(n^2 * n^2) = O(n^4).
Space Complexity
O(1) – The provided brute force algorithm checks all possible sub-array combinations. The plain English explanation describes saving the lengths of valid sub-arrays. However, it's implied that this 'saved pairs of lengths' is done by storing the smallest length found so far, not storing all possible pairs. Therefore, we only need constant extra space to store the lengths of the current best sub-arrays and a few index variables used during the iterations. No auxiliary data structures are created whose size depends on the input array's length N. Thus, the auxiliary space is O(1).
Optimal Solution
Approach
The best way to solve this problem is to find the shortest possible sequences that add up to the target, then combine the two shortest ones. We do this by first finding the shortest sequences ending at each position, and then finding the shortest sequences starting at each position.
Here's how the algorithm would work step-by-step:
- First, go through the list of numbers and for each number, find the length of the shortest sequence ending at that number that adds up to the target. If no such sequence exists, mark it with a special value (like infinity) meaning 'not possible'.
- Next, go through the list in reverse. For each number, find the length of the shortest sequence starting at that number that adds up to the target. Again, if it doesn't exist, use our special 'not possible' value.
- Now, go through the list again. For each position, add the shortest sequence ending at the previous position to the shortest sequence starting at the current position. This gives you the combined length of two non-overlapping sequences.
- Find the smallest combined length from all the positions. If the smallest length is our 'not possible' value (meaning either no starting or ending sequences could be found), then there's no solution. Otherwise, that smallest length is the answer.
Code Implementation
def find_two_non_overlapping_sub_arrays(numbers, target):
array_length = len(numbers)
shortest_length_ending_at = [float('inf')] * array_length
shortest_length_starting_at = [float('inf')] * array_length
# Find shortest subarrays ending at each index
current_sum = 0
start_index = 0
shortest_sub_array_length = float('inf')
for end_index in range(array_length):
current_sum += numbers[end_index]
while current_sum > target:
current_sum -= numbers[start_index]
start_index += 1
if current_sum == target:
shortest_sub_array_length = min(shortest_sub_array_length, end_index - start_index + 1)
shortest_length_ending_at[end_index] = shortest_sub_array_length
# Find shortest subarrays starting at each index
current_sum = 0
end_index = array_length - 1
shortest_sub_array_length = float('inf')
for start_index in range(array_length - 1, -1, -1):
current_sum += numbers[start_index]
while current_sum > target:
current_sum -= numbers[end_index]
end_index -= 1
if current_sum == target:
shortest_sub_array_length = min(shortest_sub_array_length, end_index - start_index + 1)
shortest_length_starting_at[start_index] = shortest_sub_array_length
minimum_combined_length = float('inf')
# Find the minimum combined length
for index in range(1, array_length):
minimum_combined_length = min(
minimum_combined_length,
shortest_length_ending_at[index - 1] + shortest_length_starting_at[index],
)
# Return -1 if no solution exists
if minimum_combined_length == float('inf'):
return -1
else:
return minimum_combined_lengthBig(O) Analysis
Time Complexity
O(n) – The algorithm involves three passes through the input array of size n. The first pass finds shortest subarrays ending at each index. The second pass finds shortest subarrays starting at each index. The third pass combines these results to find the minimum length. Each pass involves a sliding window approach to find subarrays with the target sum, which takes O(n) time in the worst case for each pass. Therefore, the overall time complexity is O(n) + O(n) + O(n) which simplifies to O(n).
Space Complexity
O(N) – The solution involves creating two arrays, `shortest_ending` and `shortest_starting`, to store the lengths of the shortest sub-arrays ending at and starting at each index respectively. Both of these arrays have a size equal to the number of elements in the input array, denoted as N. Therefore, the auxiliary space required is directly proportional to the size of the input array, leading to a space complexity of O(N).
Edge Cases
| Case | How to Handle |
|---|---|
| Null or empty input array | Return -1 immediately as no valid sub-arrays can exist. |
| Array size is less than two (cannot form two sub-arrays) | Return -1 since two non-overlapping sub-arrays are impossible. |
| No sub-arrays sum to the target | Return -1 if no two sub-arrays that satisfy target can be found. |
| Input array contains negative numbers | The sliding window or prefix sum approach must correctly handle negative values potentially resulting in shrinking/expanding windows. |
| Input array contains zero(s) | Zeroes can potentially form valid sub-arrays by themselves, or impact the sum calculation requiring careful handling in the sliding window/prefix sum. |
| Large array with a target sum occurring very late in the array | Ensure the solution doesn't have unnecessary iterations; potentially use early stopping or optimization within the search loops. |
| Integer overflow potential when calculating cumulative sums for large arrays or large numbers. | Use long data type for sum calculations and intermediate results to prevent overflow. |
| Multiple possible pairs of sub-arrays exist; find the minimal combined length. | Track the minimum length found so far and update it whenever a shorter valid combination is located. |
Null or empty input array
How to Handle:
Return -1 immediately as no valid sub-arrays can exist.
Array size is less than two (cannot form two sub-arrays)
How to Handle:
Return -1 since two non-overlapping sub-arrays are impossible.
No sub-arrays sum to the target
How to Handle:
Return -1 if no two sub-arrays that satisfy target can be found.
Input array contains negative numbers
How to Handle:
The sliding window or prefix sum approach must correctly handle negative values potentially resulting in shrinking/expanding windows.
Input array contains zero(s)
How to Handle:
Zeroes can potentially form valid sub-arrays by themselves, or impact the sum calculation requiring careful handling in the sliding window/prefix sum.
Large array with a target sum occurring very late in the array
How to Handle:
Ensure the solution doesn't have unnecessary iterations; potentially use early stopping or optimization within the search loops.
Integer overflow potential when calculating cumulative sums for large arrays or large numbers.
How to Handle:
Use long data type for sum calculations and intermediate results to prevent overflow.
Multiple possible pairs of sub-arrays exist; find the minimal combined length.
How to Handle:
Track the minimum length found so far and update it whenever a shorter valid combination is located.
Explore Interview QuestionsTaro 75Google Interview QuestionsMeta Interview QuestionsAmazon Interview QuestionsApple Interview QuestionsNetflix Interview Questions
Explore Interview ExperiencesOpenAI Interview ExperiencesAnthropic Interview ExperiencesPerplexity Interview ExperiencesWindsurf Interview ExperiencesMistral AI Interview Experiences
