Maximum Number of Non-Overlapping Subarrays With Sum Equals Target

Med

#1424Time: O(N^2), where N is the length of `nums`. The nested loops (one for `i` and one for `j`) result in a quadratic time complexity.Space: O(N), where N is the length of `nums`, for the `dp` array.

Patterns

Greedy Prefix Sum

Data structures

Array Hash Table

Prompt

Given an array nums and an integer target, return the maximum number of non-empty non-overlapping subarrays such that the sum of values in each subarray is equal to target.

Example 1:

Input: nums = [1,1,1,1,1], target = 2
Output: 2
Explanation: There are 2 non-overlapping subarrays [1,1,1,1,1] with sum equals to target(2).

Example 2:

Input: nums = [-1,3,5,1,4,2,-9], target = 6
Output: 2
Explanation: There are 3 subarrays with sum equal to 6.
([5,1], [4,2], [3,5,1,4,2,-9]) but only the first 2 are non-overlapping.

Constraints:

1 <= nums.length <= 10⁵
-10⁴ <= nums[i] <= 10⁴
0 <= target <= 10⁶

Approaches

2 approaches with complexity analysis and trade-offs.

This approach uses dynamic programming to solve the problem. We define dp[i] as the maximum number of non-overlapping subarrays with a sum equal to target that can be found in the suffix of the array starting from index i. The final answer will be dp[0], which is computed by iterating backward through the array and considering all possible subarrays.

Algorithm

Create a dp array of size n + 1, where n is the length of nums. Initialize all its values to 0.
Iterate i from n - 1 down to 0:
- First, assume we don't start a subarray at i. The result would be the same as for the subarray starting at i+1. So, set dp[i] = dp[i + 1].
- Initialize current_sum = 0.
- Then, try to find a subarray starting at i. Iterate j from i to n - 1:
  - Add nums[j] to current_sum.
  - If current_sum equals target, we've found a valid subarray nums[i...j].
  - This contributes 1 to the count, plus the maximum number of subarrays we can find in the remaining part of the array, which starts at index j + 1. This is given by dp[j + 1].
  - Update dp[i] to be the maximum of its current value and 1 + dp[j + 1].
The final answer is dp[0], which represents the maximum number of subarrays for the entire array nums[0...n-1].

Walkthrough

We build a dp array of size n+1, where n is the length of nums. dp[i] will store the result for the subarray nums[i:]. We initialize dp[n] to 0, as there are no subarrays in an empty array.

We iterate backward from i = n-1 down to 0. For each index i, we have two choices:

Don't start a subarray at index i: In this case, the number of subarrays is the same as the number we can find starting from i+1, which is dp[i+1]. We set dp[i] = dp[i+1] as a baseline.
Start a subarray at index i: We iterate with a second pointer j from i to n-1, calculating the sum of nums[i...j]. If this sum equals target, we have found a valid subarray. This gives us 1 subarray plus the maximum number of subarrays we can find in the rest of the array, which starts from index j+1. This value is 1 + dp[j+1]. We then update dp[i] with the maximum value found among all such valid subarrays starting at i.

After the loops complete, dp[0] contains the maximum number of non-overlapping subarrays for the entire array.

1class Solution {2    public int maxNonOverlapping(int[] nums, int target) {3        int n = nums.length;4        int[] dp = new int[n + 1];5        6        for (int i = n - 1; i >= 0; i--) {7            // Option 1: Skip the element at index i8            dp[i] = dp[i + 1];9            10            long currentSum = 0;11            // Option 2: Find a subarray starting at i12            for (int j = i; j < n; j++) {13                currentSum += nums[j];14                if (currentSum == target) {15                    // Found a subarray nums[i...j].16                    // The result is 1 + max subarrays from index j+1.17                    dp[i] = Math.max(dp[i], 1 + dp[j + 1]);18                }19            }20        }21        22        return dp[0];23    }24}

Complexity

Time

O(N^2), where N is the length of `nums`. The nested loops (one for `i` and one for `j`) result in a quadratic time complexity.

Space

O(N), where N is the length of `nums`, for the `dp` array.

Trade-offs

Pros

It is a straightforward and systematic way to explore all possibilities, guaranteeing an optimal solution.
The logic is relatively easy to understand for those familiar with dynamic programming.

Cons

The O(N^2) time complexity is inefficient for large inputs as specified by the constraints (N up to 10^5) and will likely result in a 'Time Limit Exceeded' error.

A more efficient approach is to use a greedy strategy combined with the prefix sum technique. The core idea is that whenever we find a subarray that sums to the target, we should commit to it and restart our search from the next element. This is because taking the earliest-ending subarray maximizes the length of the remaining array, thus maximizing the opportunity to find more non-overlapping subarrays. We can efficiently find these subarrays in linear time using a hash set to store prefix sums.

Algorithm

Initialize count = 0 and prefix_sum = 0.
Create a HashSet called seen_sums and add 0 to it. This initial 0 is crucial for finding subarrays that start at the beginning of a search segment.
Iterate through each number num in the nums array:
- Update prefix_sum by adding num to it.
- Check if prefix_sum - target exists in seen_sums.
  - If it exists, it means we have found a subarray ending at the current position with the desired sum.
    - Increment count.
    - To ensure the next subarray is non-overlapping, we must reset our search. Set prefix_sum = 0, clear seen_sums, and add 0 back to it.
  - If it does not exist, it means no subarray ending at the current position sums to target.
    - Add the current prefix_sum to seen_sums to be used for future checks.
After iterating through the entire array, return count.

Walkthrough

We iterate through the array from left to right, maintaining a current_prefix_sum. We also use a HashSet to store the prefix sums encountered since the last found subarray (or from the beginning).

At each index i, we update current_prefix_sum. To check if a subarray ending at i has a sum of target, we need to see if current_prefix_sum - target exists in our set of previously seen prefix sums. This is based on the property that sum(nums[j+1...i]) = prefix_sum[i] - prefix_sum[j]. If we want this sum to be target, we need to find a j such that prefix_sum[j] = current_prefix_sum - target.

If we find such a prefix sum in our set, we've found a valid subarray. Following the greedy strategy, we increment our count of non-overlapping subarrays. Then, to ensure the next subarray we find is non-overlapping, we 'reset' our search. This is done by clearing the HashSet and re-initializing it with just 0 (to handle subarrays that start from the next element). We also effectively reset the current_prefix_sum to 0 relative to the new starting point.

1import java.util.HashSet;2import java.util.Set;3 4class Solution {5    public int maxNonOverlapping(int[] nums, int target) {6        // Use a set to store prefix sums encountered in the current search window.7        Set<Long> seenSums = new HashSet<>();8        // Add 0 to handle subarrays that start from the beginning of a search segment.9        seenSums.add(0L); 10        11        int count = 0;12        long currentSum = 0;13        14        for (int num : nums) {15            currentSum += num;16            if (seenSums.contains(currentSum - target)) {17                // Found a subarray with the target sum.18                count++;19                // Reset for the next non-overlapping subarray search.20                currentSum = 0;21                seenSums.clear();22                seenSums.add(0L);23            } else {24                // Add the current prefix sum to the set for future checks.25                seenSums.add(currentSum);26            }27        }28        29        return count;30    }31}

Complexity

Time

O(N), where N is the length of `nums`. We iterate through the array only once, and `HashSet` lookups and insertions take, on average, O(1) time.

Space

O(N) in the worst case, where N is the length of `nums`. The `HashSet` could store up to N distinct prefix sums if no target-sum subarray is found and all prefix sums are unique.

Trade-offs

Pros

Highly efficient with O(N) time complexity, making it suitable for large inputs.
The implementation is concise and elegantly combines the prefix sum technique with a greedy choice.

Cons

The correctness of the greedy strategy is not immediately obvious and relies on the insight that taking the shortest possible subarray is always optimal.
The space complexity is O(N) in the worst-case, which might be a concern for extremely memory-constrained environments, although it's generally acceptable.

Solutions

Solution

1class Solution { public int maxNonOverlapping ( int [] nums , int target ) { int ans = 0 , n = nums . length ; for ( int i = 0 ; i < n ; ++ i ) { Set < Integer > vis = new HashSet <>(); int s = 0 ; vis . add ( 0 ); while ( i < n ) { s += nums [ i ]; if ( vis . contains ( s - target )) { ++ ans ; break ; } ++ i ; vis . add ( s ); } } return ans ; } }

1class Solution {2public:3  int maxNonOverlapping(vector<int> &nums, int target) {4    int ans = 0, n = nums.size();5    for (int i = 0; i < n; ++i) {6      unordered_set<int> vis{{0}};7      int s = 0;8      while (i < n) {9        s += nums[i];10        if (vis.count(s - target)) {11          ++ans;12          break;13        }14        ++i;15        vis.insert(s);16      }17    }18    return ans;19  }20};

1class Solution:2    def maxNonOverlapping(self, nums: List[int], target: int) -> int: ans = 0 i, n = 0, len(nums) while i < n: s = 0 vis = {0} while i < n: s += nums[i] if s - target in vis: ans += 1 break i += 1 vis . add(s) i += 1 return ans

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem