LeetCode 1546 - Maximum Number of Non-Overlapping Subarrays With Sum Equals Target

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Greedy, Prefix Sum

Solution

Problem Understanding

This problem asks us to find the maximum number of non-overlapping subarrays in a given integer array nums such that the sum of each subarray equals a given target. In simpler terms, we are scanning the array to find consecutive sequences of numbers whose sum matches target and ensuring that no two chosen sequences share any elements. The challenge is to maximize the count of such sequences.

The input nums can contain negative numbers, zero, or positive numbers. The array length can be up to 10^5, which rules out brute-force solutions that consider every possible subarray. The output is a single integer representing the maximum number of subarrays meeting the conditions.

Important observations include that subarrays must be contiguous and non-empty, and subarrays cannot overlap. Edge cases to consider include arrays where all numbers are zero, arrays with negative numbers summing to the target, and cases where the target itself is zero.

Approaches

The brute-force approach would consider every possible subarray of nums, calculate its sum, and check if it equals target. For each valid subarray, we would try to count it while ensuring no overlap. This guarantees correctness but is too slow for large arrays since the number of subarrays grows quadratically with the array length.

The optimal approach relies on the prefix sum technique combined with a hash set. The key insight is that if the sum of elements from index i to j equals target, then the difference between the prefix sums at j and i-1 equals target. By tracking all seen prefix sums and resetting them whenever we find a valid subarray, we can greedily maximize the count of non-overlapping subarrays in linear time.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Checks all subarrays explicitly; too slow for n up to 10^5
Optimal	O(n)	O(n)	Uses prefix sums and a hash set to detect valid subarrays greedily

Algorithm Walkthrough

Initialize a variable count to 0 to keep track of the number of non-overlapping subarrays found.
Initialize a variable current_sum to 0 to maintain the running prefix sum.
Initialize a hash set seen_sums and add 0 to it. The 0 accounts for a subarray starting at the first element.
Iterate through each number in nums:
Add the current number to current_sum.
Check if current_sum - target exists in seen_sums. If it does, it means there is a subarray ending at the current index whose sum equals target.
If a valid subarray is found, increment count, reset current_sum to 0, and clear seen_sums, then add 0 back to seen_sums to handle future subarrays.
If no valid subarray is found, add current_sum to seen_sums.
After the loop, return count.

Why it works: The hash set keeps track of all prefix sums since the last counted subarray. When current_sum - target is found in seen_sums, we know a valid non-overlapping subarray exists. Resetting the state ensures subsequent subarrays do not overlap with already counted ones.

Python Solution

from typing import List

class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        count = 0
        current_sum = 0
        seen_sums = set()
        seen_sums.add(0)
        
        for num in nums:
            current_sum += num
            if current_sum - target in seen_sums:
                count += 1
                current_sum = 0
                seen_sums.clear()
                seen_sums.add(0)
            else:
                seen_sums.add(current_sum)
        
        return count

The Python implementation follows the algorithm directly. seen_sums stores prefix sums since the last counted subarray. If the difference current_sum - target exists, we found a valid subarray and reset the state for future non-overlapping subarrays.

Go Solution

func maxNonOverlapping(nums []int, target int) int {
    count := 0
    currentSum := 0
    seenSums := make(map[int]struct{})
    seenSums[0] = struct{}{}
    
    for _, num := range nums {
        currentSum += num
        if _, exists := seenSums[currentSum - target]; exists {
            count++
            currentSum = 0
            seenSums = make(map[int]struct{})
            seenSums[0] = struct{}{}
        } else {
            seenSums[currentSum] = struct{}{}
        }
    }
    
    return count
}

In Go, a map is used instead of a set, where keys are the prefix sums and values are empty structs. Otherwise, the logic mirrors the Python version. Map initialization and resetting are explicit in Go.

Worked Examples

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

Index	num	current_sum	seen_sums	current_sum - target	count
0	1	1	{0,1}	-1	0
1	1	2	{0,1}	0	1
2	1	1	{0,1}	-1	1
3	1	2	{0,1}	0	2
4	1	1	{0,1}	-1	2

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

Index	num	current_sum	seen_sums	current_sum - target	count
0	-1	-1	{0,-1}	-7	0
1	3	2	{0,-1,2}	-4	0
2	5	7	{0,-1,2,7}	1	0
3	1	8	{0,-1,2,7,8}	2	0
4	4	12	{0,-1,2,7,8,12}	6	1
5	2	2	{0,2}	-4	1
6	-9	-7	{0,2,-7}	-13	1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	We iterate through `nums` once, and set/map operations are O(1) on average
Space	O(n)	The hash set may store up to n prefix sums in the worst case

The linear time complexity is achievable because we avoid nested loops and maintain a running sum, leveraging the hash set to quickly detect subarrays that sum to the target.

Test Cases

# Provided examples
assert Solution().maxNonOverlapping([1,1,1,1,1], 2) == 2  # Example 1
assert Solution().maxNonOverlapping([-1,3,5,1,4,2,-9], 6) == 2  # Example 2

# Edge cases
assert Solution().maxNonOverlapping([0,0,0,0], 0) == 4  # All zeros, target zero
assert Solution().maxNonOverlapping([1,2,3,4,5], 15) == 1  # Entire array sums to target
assert Solution().maxNonOverlapping([1,-1,1,-1,1,-1], 0) == 3  # Alternating positive and negative
assert Solution().maxNonOverlapping([1,2,3], 7) == 0  # No subarray sums to target

Test	Why
[1,1,1,1,1], 2	Basic functionality with multiple non-overlapping subarrays
[-1,3,5,1,4,2,-9], 6	Handles negative numbers and multiple subarrays
[0,0,0,0], 0	Tests zero elements and target
[1,2,3,4,5], 15	Subarray is the entire array
[1,-1,1,-1,1,-1], 0	Alternating positives/negatives and zero target
[1,2,3], 7	No valid subarrays,