Problem Description

You are given an array nums and an integer target. Your task is to find the maximum number of non-empty, non-overlapping subarrays where each subarray's sum equals target.

A subarray is a contiguous sequence of elements from the array. Non-overlapping means that no two subarrays can share any elements - once an element is used in one subarray, it cannot be used in another.

For example, if nums = [1, 1, 1, 1, 1] and target = 2, you could have subarrays [1, 1] at indices 0-1 and [1, 1] at indices 2-3, giving you a maximum of 2 non-overlapping subarrays with sum equal to 2.

The goal is to maximize the count of such valid subarrays. You need to return this maximum count as an integer.

Intuition

The key insight is that we want to maximize the number of subarrays, so we should use a greedy approach - whenever we find a valid subarray with sum equal to target, we should immediately take it. This is optimal because taking a subarray earlier never prevents us from finding more subarrays later, but waiting might cause us to miss opportunities.

To find subarrays with a specific sum efficiently, we can use the prefix sum technique. As we traverse the array, we maintain a running sum s. For any position i, if we want to find if there's a subarray ending at i with sum equal to target, we need to check if there was a previous position j where the prefix sum was s - target. This is because the subarray from j+1 to i would have sum s - (s - target) = target.

We use a hash set vis to store all prefix sums we've seen so far. We initialize it with 0 to handle the case where a subarray starting from the beginning has sum equal to target.

The clever part is the reset mechanism: once we find a valid subarray, we increment our answer and then reset everything - we clear our prefix sum and hash set, and continue searching from the next position. This ensures our subarrays don't overlap, as we essentially start fresh after finding each valid subarray.

This greedy strategy combined with prefix sum gives us an efficient way to find the maximum number of non-overlapping subarrays with the target sum.

Learn more about Greedy and Prefix Sum patterns.

Solution Approach

The solution implements a greedy approach with prefix sum and hash table to find the maximum number of non-overlapping subarrays.

We use two pointers to traverse the array:

• An outer pointer i that marks our current position in the array
• The same pointer i is reused in the inner loop to continue traversing

Here's how the algorithm works step by step:

1. Initialize variables: We start with ans = 0 to count valid subarrays, and i = 0 to track our position in the array of length n.

2. Outer loop: While i < n, we begin searching for the next valid subarray starting from position i.

3. Reset for new search: For each new search:

   • Initialize prefix sum s = 0
   • Create a hash set vis = {0} to store seen prefix sums (initialized with 0 to handle subarrays starting from current position)

4. Inner loop - Finding valid subarray:

   • Add current element to prefix sum: s += nums[i]
   • Check if s - target exists in vis. If it does, we've found a valid subarray:
     • The subarray sum from some previous position to current position equals target
     • Increment ans += 1
     • Break from inner loop to start searching for the next non-overlapping subarray
   • Move to next position: i += 1
   • Add current prefix sum to hash set: vis.add(s)

5. Move past current subarray: After the inner loop (whether we found a valid subarray or reached a position where no valid subarray exists), increment i += 1 to ensure we don't reuse elements.

6. Return result: After traversing the entire array, return ans as the maximum count of non-overlapping subarrays.

The time complexity is O(n) where n is the length of the array, as each element is visited at most twice. The space complexity is O(n) in the worst case for the hash set storing prefix sums.

Example Walkthrough

Let's walk through the algorithm with nums = [1, 1, 1, 1, 1] and target = 2.

Initial State:

• ans = 0, i = 0, n = 5

First Search (starting at i=0):

• Initialize: s = 0, vis = {0}
• i=0: s = 0 + 1 = 1, check if 1 - 2 = -1 in vis? No. Add 1 to vis. vis = {0, 1}, i = 1
• i=1: s = 1 + 1 = 2, check if 2 - 2 = 0 in vis? Yes!
  • Found subarray [1,1] with sum 2
  • ans = 1, break inner loop
• Move past subarray: i = 2

Second Search (starting at i=2):

• Initialize: s = 0, vis = {0}
• i=2: s = 0 + 1 = 1, check if 1 - 2 = -1 in vis? No. Add 1 to vis. vis = {0, 1}, i = 3
• i=3: s = 1 + 1 = 2, check if 2 - 2 = 0 in vis? Yes!
  • Found subarray [1,1] with sum 2
  • ans = 2, break inner loop
• Move past subarray: i = 4

Third Search (starting at i=4):

• Initialize: s = 0, vis = {0}
• i=4: s = 0 + 1 = 1, check if 1 - 2 = -1 in vis? No. Add 1 to vis. vis = {0, 1}, i = 5
• i=5: Out of bounds, exit inner loop
• Move past: i = 6

End: i = 6 >= n, exit outer loop

Result: Return ans = 2

The algorithm found two non-overlapping subarrays [1,1] at indices 0-1 and [1,1] at indices 2-3, each with sum equal to 2.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the array nums. Although there are two nested while loops, each element is visited at most once. The outer loop starts at position i and continues until the end of the array. When the inner loop finds a subarray with sum equal to target (when s - target in vis), it breaks and moves i forward by 1. The key observation is that after finding a valid subarray, we skip to the next position after the subarray ends, ensuring no overlapping. Each element is processed exactly once through the entire execution, resulting in linear time complexity.

The space complexity is O(n), where n is the length of the array nums. The set vis stores prefix sums encountered during the traversal. In the worst case, when no valid subarray is found in a single pass through the array, the set vis could store up to n different prefix sums (one for each position in the array). The set is reset for each new starting position when searching for the next non-overlapping subarray, but the maximum space used at any point is still O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall: Incorrectly Resetting the Hash Set Position

A critical pitfall in this solution is the timing of when we add the current prefix sum to the hash set. In the provided code, seen_prefix_sums.add(current_sum) happens after index += 1. This creates a subtle bug where the prefix sum at position i is associated with position i+1, leading to incorrect subarray boundary detection.

Why this is problematic:

• When we find current_sum - target in seen_prefix_sums, we're actually identifying a subarray that ends at the previous position, not the current one
• This off-by-one error can cause us to miss valid subarrays or incorrectly identify overlapping ones

Example demonstrating the issue:

nums = [1, 2, 3], target = 3
# At index 0: current_sum = 1, check if 1-3=-2 in {0} (No)
# Then index becomes 1, add current_sum=1 to set
# At index 1: current_sum = 3, check if 3-3=0 in {0,1} (Yes!)
# But we break at index 1, when the valid subarray [1,2] actually ends at index 1
# The confusion arises from adding prefix sum after incrementing index

Solution: Add Prefix Sum Before Incrementing Index

The correct approach is to add the current prefix sum to the hash set before incrementing the index:

class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        result = 0
        index = 0
        length = len(nums)
      
        while index < length:
            current_sum = 0
            seen_prefix_sums = {0}
          
            while index < length:
                current_sum += nums[index]
              
                if current_sum - target in seen_prefix_sums:
                    result += 1
                    break
              
                # Add prefix sum BEFORE incrementing index
                seen_prefix_sums.add(current_sum)
                index += 1
          
            index += 1
      
        return result

Key differences:

1. We add current_sum to seen_prefix_sums immediately after checking for a valid subarray
2. This ensures that the prefix sum at position i is correctly associated with position i
3. The logic flow becomes clearer: process current position → store its prefix sum → move to next position

This correction ensures that subarray boundaries are correctly identified and we maximize the count of non-overlapping subarrays with the target sum.