Leetcode 1546: Maximum Number of Non-Overlapping Subarrays With Sum Equals Target
Given an integer array nums and an integer target, return the maximum number of non-empty, non-overlapping subarrays that sum up to the target.
Problem
Approach
Steps
Complexity
Input: The input consists of an array of integers nums and an integer target. The array nums contains the elements of the array, and target is the sum we want to find in non-overlapping subarrays.
Example: nums = [1, 1, 1, 1, 1], target = 2
Constraints:
• 1 <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4
• 0 <= target <= 10^6
Output: Return the maximum number of non-overlapping subarrays where each subarray's sum equals the target.
Example: Output: 2
Constraints:
• The subarrays must be non-overlapping, and each must sum up to the target.
Goal: The goal is to efficiently find the maximum number of non-overlapping subarrays with a sum equal to the target.
Steps:
• 1. Track the sum of elements in the current subarray.
• 2. When the sum equals the target, count the subarray and reset the sum to start a new subarray.
• 3. Skip overlapping subarrays to ensure non-overlapping subarrays are counted.
Goal: The solution must handle large arrays efficiently due to the constraints.
Steps:
• 1 <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4
• 0 <= target <= 10^6
Assumptions:
• It is assumed that the input array nums is non-empty, and target is a valid integer.
• Input: nums = [1, 1, 1, 1, 1], target = 2
• Explanation: There are two non-overlapping subarrays that sum up to the target: [1, 1] and [1, 1].
• Input: nums = [-1, 3, 5, 1, 4, 2, -9], target = 6
• Explanation: There are multiple subarrays that sum to 6, but only two non-overlapping subarrays count: [5, 1] and [4, 2].
Approach: We can approach this problem by iterating through the array while maintaining a running sum of elements. Whenever the sum matches the target, we count the subarray and reset the sum to start a new subarray.
Observations:
• We need to avoid overlapping subarrays. Once we find a valid subarray, we should reset the sum and continue searching.
• A greedy approach will work where we continuously look for subarrays with the sum equal to the target and ensure that they don't overlap.
Steps:
• 1. Initialize a variable to track the running sum.
• 2. Traverse through the array and add each element to the running sum.
• 3. If the running sum equals the target, increment the count and reset the sum to zero.
• 4. Continue iterating and keep track of the maximum number of valid subarrays.
Empty Inputs:
• The input array is always non-empty according to the constraints.
Large Inputs:
• For large inputs, ensure the solution handles the array efficiently in linear time.
Special Values:
• If the target is 0, handle cases where the subarrays sum to zero, such as when the array contains consecutive zeros.
Constraints:
• Ensure the solution runs within time limits for all values of n and target.
int maxNonOverlapping(vector<int>& nums, int hit) {
map<int, int> mp;
int n = nums.size(), sum = 0, right = -1, cnt = 0;
//partial_sum(nums.begin(), nums.end(), nums.begin());
mp[0] = -1;
for(int i = 0; i < n;i++){
//cout<< nums[i] << " ";
sum += nums[i];
if(mp.count(sum - hit)) {
int left = mp[sum - hit];
// cout << right << " " << left;
if (right <= left) {
cnt++;
right = i;
}
}
mp[sum] = i;
// cout<< mp[sum] << endl;
}
return cnt;
}
1 : Function Declaration
int maxNonOverlapping(vector<int>& nums, int hit) {
This is the function declaration where `maxNonOverlapping` is defined to take a vector of integers `nums` and an integer `hit` as input, and returns an integer representing the maximum number of non-overlapping subarrays whose sum equals `hit`.
2 : Map Initialization
map<int, int> mp;
A map `mp` is created to store cumulative sums as keys and their corresponding indices as values, which will help to track if a certain sum (sum - hit) exists to form non-overlapping subarrays.
3 : Variable Initialization
int n = nums.size(), sum = 0, right = -1, cnt = 0;
The variables are initialized: `n` stores the size of the `nums` vector, `sum` keeps track of the cumulative sum, `right` stores the index of the last valid subarray, and `cnt` tracks the number of valid subarrays.
4 : Map Initialization
mp[0] = -1;
Initialize the map with a key-value pair of `0: -1` to handle cases where a subarray starting from index 0 sums to `hit`.
5 : For Loop
for(int i = 0; i < n; i++) {
A for loop that iterates over each element in the `nums` vector.
6 : Sum Update
sum += nums[i];
Update the cumulative sum by adding the current element `nums[i]`.
7 : Condition Check
if(mp.count(sum - hit)) {
Check if the map contains the key `sum - hit`, which would indicate that a subarray with sum `hit` exists.
8 : Map Lookup
int left = mp[sum - hit];
If the condition is true, get the index of the subarray's left boundary from the map.
9 : Condition Check
if (right <= left) {
Check if the current subarray is non-overlapping by ensuring that the `right` boundary is less than or equal to the `left` boundary.
10 : Count Update
cnt++;
If the subarray is non-overlapping, increment the counter `cnt`.
11 : Right Update
right = i;
Update the `right` boundary to the current index `i` to mark the end of the last valid subarray.
12 : Map Update
mp[sum] = i;
Add or update the map with the current cumulative sum `sum` and its corresponding index `i`.
13 : Return Statement
return cnt;
Return the count of non-overlapping subarrays whose sum equals `hit`.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: The solution iterates through the array once, making the time complexity O(n).
Best Case: O(1)
Worst Case: O(1)
Description: The space complexity is O(1) because we only use a constant amount of extra space.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus