Maximum Number of Non-Overlapping Subarrays With Sum Equals Target

LeetCode 1546, Maximum Number of Non-Overlapping Subarrays With Sum Equals Target, combines two classic patterns into one problem: prefix sums for detecting subarray sums, and a greedy strategy for maximizing non-overlapping selections. If you have solved Subarray Sum Equals K and Non-overlapping Intervals, you already have every building block you need.

The problem

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 equals target.

nums = [1, 1, 1, 1, 1], target = 2  ->  2
nums = [-1, 3, 5, 1, 4, 2, -9], target = 6  ->  2
nums = [-2, 6, 6, 3, 5, 4, 1, 2, 8], target = 10  ->  3

Why greedy works

You might be tempted to find all subarrays that sum to the target and then solve an interval scheduling problem on them. That works, but it is overkill. There is a simpler greedy observation: whenever you find a valid subarray, always take it immediately and reset your tracking. Taking the earliest-ending subarray is always at least as good as waiting for a later one, because it leaves the most room for future subarrays to fit.

This is the same reasoning behind the classic activity selection problem: sort by end time, always pick the earliest finish. Here, you do not even need to sort because you are scanning left to right, so the first valid subarray you encounter at each position already ends as early as possible.

The approach

The algorithm combines prefix sums with a greedy reset:

1. Maintain a running prefix_sum as you scan through the array.
2. Keep a set seen of all prefix sums encountered since the last reset. Initialize it with {0}.
3. At each index, compute prefix_sum and check whether prefix_sum - target is in seen.
4. If it is, you have found a subarray that sums to target. Increment your count, and reset seen to contain only the current prefix_sum. This reset ensures the next subarray you find will not overlap with the one you just took.
5. If it is not, add prefix_sum to seen and continue.

The reset is the key insight. In Subarray Sum Equals K, you keep a running frequency map of all prefix sums because you want to count every valid subarray, overlapping or not. Here, you want non-overlapping subarrays, so once you commit to one, you wipe the slate clean and start fresh.

The solution

def maxNonOverlapping(nums, target):
    prefix_sum = 0
    seen = {0}
    count = 0

    for num in nums:
        prefix_sum += num
        if prefix_sum - target in seen:
            count += 1
            seen = {prefix_sum}
        else:
            seen.add(prefix_sum)

    return count

Here is how it works:

1. Seed the set with {0}. This allows detection of subarrays that start at the very beginning of the array.

2. Accumulate the prefix sum. For each element, add it to the running total.

3. Check for prefix_sum - target in the set. If the difference exists, some earlier prefix sum marks the start of a valid subarray ending at the current index.

4. Take the subarray greedily. Increment the count and reset seen to {prefix_sum}. The reset prevents any future subarray from overlapping with this one.

5. Otherwise, record the prefix sum. Add it to the set so future elements can reference it.

Step-by-step walkthrough

Let's trace through nums = [1, 1, 1, 1, 1] with target = 2. The prefix sums are 0, 1, 2, 3, 4, 5. Watch how the set gets reset each time we find a valid subarray.

The algorithm finds two non-overlapping subarrays: [1, 1] at indices 0-1 and [1, 1] at indices 2-3. The last element at index 4 cannot form a valid pair on its own, so it goes unused.

Complexity analysis

Time: O(n). You iterate through the array once. Each set lookup and insertion is O(1) on average, so the total work is linear. The resets do not add extra cost because each prefix sum is inserted into the set at most once between resets.

Space: O(n). The set can hold at most n + 1 prefix sums between resets. In the worst case (no valid subarrays found), the set grows to hold every distinct prefix sum.

The building blocks

Prefix sum for subarray sums

The prefix sum technique converts a subarray sum question into a difference question: "does prefix_sum[j] - prefix_sum[i] equal the target?" By storing previously seen prefix sums, you answer that question in O(1) per element. This is the same mechanic behind Subarray Sum Equals K, where a frequency map counts all matching subarrays. Here, a simple set suffices because you only need to know whether a match exists, not how many.

Greedy interval selection via reset

Instead of collecting all valid subarrays and running an interval scheduling algorithm, you use a greedy reset. The moment you find a valid subarray, you take it and clear your tracking state. This mirrors the activity selection strategy from Non-overlapping Intervals: always pick the interval that finishes earliest, which leaves the most room for future intervals. Since you scan left to right, the first valid subarray you find at any point is already the earliest-ending one.

Edge cases

• No valid subarrays. If no subarray sums to the target, the set never triggers a match. The answer is 0.
• Entire array sums to target. The prefix sum after the last element minus the seed (0) equals the target. One subarray is found.
• target = 0. You are looking for subarrays that sum to 0. The algorithm handles this correctly because prefix_sum - 0 = prefix_sum, and the set tracks when a prefix sum repeats.
• Negative numbers. Prefix sums can increase and decrease. The set-based approach works regardless of sign, unlike sliding window techniques.
• Single element equal to target. The prefix sum after that element minus 0 (the seed) equals the target. One match is found.
• All elements equal to target. Each single element forms a valid subarray. The greedy reset ensures you take every one. Answer: n.
• Overlapping candidates. If [0, 2] and [1, 3] both sum to the target, the algorithm takes [0, 2] first (it ends earlier) and resets. It then checks whether [3, ...] can form another subarray. This greedy choice is optimal.

From understanding to recall

The prefix sum + greedy reset pattern is compact: a running sum, a set, and a reset on match. But there are details that matter under pressure. You need to seed the set with {0}. You need to reset (not just clear) the set to {prefix_sum} after finding a match. You need to understand why a set works here instead of the frequency map used in Subarray Sum Equals K.

Spaced repetition drills these details until they become automatic. After a few review sessions, you will write the solution from memory and recognize instantly when a subarray problem calls for the greedy reset versus the frequency count approach.

Related posts

• Subarray Sum Equals K - The prefix sum + hash map pattern for counting all subarrays that sum to k
• Non-overlapping Intervals - Greedy interval selection by sorting on end time
• Maximum Subarray - Kadane's algorithm for finding the subarray with the largest sum