Leetcode 1477: Find Two Non-overlapping Sub-arrays Each With Target Sum
You are given an array of integers arr and an integer target. You need to find two non-overlapping sub-arrays of arr each with a sum equal target. The goal is to minimize the sum of their lengths, and if no such sub-arrays exist, return -1.
Problem
Approach
Steps
Complexity
Input: The input consists of an integer array arr and an integer target.
Example: [1, 1, 1, 2, 3], 2
Constraints:
• 1 <= arr.length <= 10^5
• 1 <= arr[i] <= 1000
• 1 <= target <= 10^8
Output: The output should return the minimum sum of the lengths of the two sub-arrays, or -1 if no such sub-arrays exist.
Example: 2
Constraints:
• If no two sub-arrays with sum equal to target exist, return -1.
Goal: The goal is to efficiently find two non-overlapping sub-arrays that sum to the target and minimize the sum of their lengths.
Steps:
• Use a sliding window approach to find all sub-arrays that sum to the target.
• Store the lengths of valid sub-arrays and ensure they do not overlap.
• Track the minimum sum of lengths for valid sub-arrays.
Goal: Ensure the input size does not exceed the constraints and that the array elements and target are within the given limits.
Steps:
• 1 <= arr.length <= 10^5
• 1 <= arr[i] <= 1000
• 1 <= target <= 10^8
Assumptions:
• The array will contain at least one sub-array summing to the target.
• Input: [1, 1, 1, 2, 3], 2
• Explanation: Here, two sub-arrays sum to 2: [1, 1] and [2], and the sum of their lengths is 2.
Approach: The approach uses a sliding window to efficiently find all sub-arrays that sum to the target and then minimizes the sum of the lengths of non-overlapping sub-arrays.
Observations:
• We need to consider non-overlapping sub-arrays, so after finding one, we must avoid overlapping with the second.
• Sliding window is an efficient way to find sub-arrays with a fixed sum.
Steps:
• Iterate through the array using a sliding window approach to find sub-arrays that sum to the target.
• Track the lengths of these sub-arrays.
• Check for non-overlapping sub-arrays and compute the minimum sum of their lengths.
Empty Inputs:
• Empty arrays should return -1.
Large Inputs:
• For large arrays, the solution should be optimized for time efficiency.
Special Values:
• Handle cases where no valid sub-arrays exist.
Constraints:
• Ensure the solution handles arrays with up to 10^5 elements.
int minSumOfLengths(vector<int>& arr, int target) {
unordered_map<int, int> mp;
int sum = 0, lsize = INT_MAX, result = INT_MAX;
mp[0] = -1;
for(int i = 0; i < arr.size(); i++) {
sum += arr[i];
mp[sum] = i;
}
sum = 0;
for(int i = 0; i < arr.size(); i++) {
sum += arr[i];
if(mp.count(sum - target))
lsize = min(lsize, i - mp[sum-target]);
if(mp.count(sum + target) && lsize < INT_MAX)
result = min(result, mp[sum + target] -i +lsize);
}
return result == INT_MAX ? -1: result;
}
1 : Method
int minSumOfLengths(vector<int>& arr, int target) {
This is the definition of the function `minSumOfLengths`, which takes an array `arr` and a target sum `target` as parameters.
2 : Declaration
unordered_map<int, int> mp;
An unordered map `mp` is declared to store cumulative sums and their corresponding indices. This helps to efficiently find subarrays whose sum is equal to a given target.
3 : Initialization
int sum = 0, lsize = INT_MAX, result = INT_MAX;
The variables are initialized: `sum` stores the cumulative sum of the elements, `lsize` is used to track the smallest subarray length, and `result` will store the minimum sum of lengths of the valid subarrays.
4 : Initialization
mp[0] = -1;
The hash map `mp` is initialized with a base case where the cumulative sum `0` is mapped to index `-1`. This helps handle edge cases like when a valid subarray starts at the beginning of the array.
5 : Loop
for(int i = 0; i < arr.size(); i++) {
This is the start of the first loop, which iterates through the array `arr` to calculate cumulative sums.
6 : Update
sum += arr[i];
In this step, the current element `arr[i]` is added to the cumulative sum `sum`.
7 : Update
mp[sum] = i;
The current cumulative sum is stored in the map `mp`, with the index `i` as its value.
8 : Initialization
sum = 0;
The cumulative sum is reset to zero for the second loop to calculate possible valid subarrays.
9 : Loop
for(int i = 0; i < arr.size(); i++) {
Start of the second loop, which processes the array again to check for subarrays that sum up to the target.
10 : Update
sum += arr[i];
The current element `arr[i]` is added to the cumulative sum again.
11 : Condition
if(mp.count(sum - target))
This condition checks if there is a subarray in `mp` whose sum is equal to `sum - target`, indicating a valid subarray.
12 : Update
lsize = min(lsize, i - mp[sum-target]);
If the condition is true, the length of the current subarray is calculated and the smallest subarray length (`lsize`) is updated.
13 : Condition
if(mp.count(sum + target) && lsize < INT_MAX)
This condition checks if there is another subarray in `mp` whose sum is equal to `sum + target` and ensures that a valid subarray length (`lsize`) has been found.
14 : Update
result = min(result, mp[sum + target] -i +lsize);
If both conditions are met, the `result` is updated with the minimum sum of lengths of the valid subarrays.
15 : Return
return result == INT_MAX ? -1: result;
The function returns the minimum sum of lengths of the valid subarrays found. If no valid subarrays exist, `-1` is returned.
Best Case: O(n) for the sliding window approach if all sub-arrays are found early.
Average Case: O(n) for iterating through the array and checking sub-array sums.
Worst Case: O(n) in the worst case where we need to examine every element.
Description: Time complexity is linear with respect to the size of the array.
Best Case: O(1) if we are able to immediately return the result.
Worst Case: O(n) if we need to store all sub-array sums and lengths.
Description: Space complexity depends on the need to store sub-array lengths, which could scale with the size of the input.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus