MediumArrayHash TableGreedyPrefix Sum

Maximum Number of Non-Overlapping Subarrays With Sum Equals Target

1 approach, code in every language

You are given an integer array and an integer target. A candidate is any contiguous subarray whose elements add up to exactly the target value.

Select as many of these candidate subarrays as possible such that no two chosen subarrays share an index. Return the maximum count of non-overlapping subarrays you can pick.

Example 1

Input: nums = [1,1,1,1,1], target = 2

Output: 2

Two disjoint pairs such as indices [0,1] and [2,3] each sum to 2. A third disjoint pair cannot fit in the single leftover element.

Example 2

Input: nums = [-1,3,5,1,4,2,-9], target = 6

Output: 2

The subarrays [5,1] and [4,2] both sum to 6 and do not overlap, giving a maximum count of 2.

Constraints

1 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4
0 <= target <= 10^6

Prefix Sums with Greedy Cut

Track prefix sums seen since the last cut; whenever currentPrefix - target has appeared, greedily close a subarray and reset the window.

Loading animation…

Intuition

A subarray from j+1 to i sums to target exactly when prefix[i] - prefix[j] equals target, i.e. prefix[i] - target equals some earlier prefix. To maximize disjoint pieces, we should close a subarray as early as possible, because an earlier cut never hurts future choices. So we keep a set of prefix sums observed since the previous cut, and the instant currentPrefix - target is present in that set we claim a subarray. After claiming, we clear the set and treat the position right after the cut as a fresh start (prefix reset to 0). This greedy leaves the largest possible tail available for more subarrays.

Algorithm walkthrough

1Initialize a running prefix sum of 0 and a set seeded with the value 0 (the empty prefix).
2Walk through the array, adding each element to the running prefix.
3Check whether prefix - target already exists in the set; if so a valid subarray ends here.
4On a hit, increment the answer, reset the prefix to 0, and reset the set to just {0} so the next window starts fresh after the cut.
5Otherwise insert the current prefix into the set and keep scanning.
6Return the accumulated count once the scan completes.

Implementation

class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        count = 0
        prefix = 0
        seen = {0}
        for num in nums:
            prefix += num
            if prefix - target in seen:
                count += 1
                prefix = 0
                seen = {0}
            else:
                seen.add(prefix)
        return count

Time

O(n)

Space

O(n)

Each element is processed once with average O(1) hash operations. The set may hold up to O(n) prefix sums between cuts.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Dynamic Programming

After the pattern

Now solve one you haven't seen.

Reading a pattern isn't the same as using it. The practice set has 1,194 original problems on the same techniques, each graded in your browser.

Open the practice set Start the FDE path

1,194 problems · 15,062 graded tests · free