Code Implementation

class Solution:
    def maxNonOverlapping(self, nums, target):
        count = 0
        prefix_sum = 0
        seen = set([0])
        for num in nums:
            prefix_sum += num
            if prefix_sum - target in seen:
                count += 1
                prefix_sum = 0
                seen = set([0])
            else:
                seen.add(prefix_sum)
        return count
      

class Solution {
public:
    int maxNonOverlapping(vector<int>& nums, int target) {
        int count = 0;
        int prefix_sum = 0;
        unordered_set<int> seen = {0};
        for (int num : nums) {
            prefix_sum += num;
            if (seen.count(prefix_sum - target)) {
                count++;
                prefix_sum = 0;
                seen.clear();
                seen.insert(0);
            } else {
                seen.insert(prefix_sum);
            }
        }
        return count;
    }
};
      

class Solution {
    public int maxNonOverlapping(int[] nums, int target) {
        int count = 0;
        int prefixSum = 0;
        Set<Integer> seen = new HashSet<>();
        seen.add(0);
        for (int num : nums) {
            prefixSum += num;
            if (seen.contains(prefixSum - target)) {
                count++;
                prefixSum = 0;
                seen.clear();
                seen.add(0);
            } else {
                seen.add(prefixSum);
            }
        }
        return count;
    }
}
      

var maxNonOverlapping = function(nums, target) {
    let count = 0;
    let prefixSum = 0;
    let seen = new Set([0]);
    for (let num of nums) {
        prefixSum += num;
        if (seen.has(prefixSum - target)) {
            count++;
            prefixSum = 0;
            seen = new Set([0]);
        } else {
            seen.add(prefixSum);
        }
    }
    return count;
};
      

Problem Description

You are given an array of integers nums and an integer target. Your task is to find the maximum number of non-overlapping subarrays whose sum is exactly equal to target.

Each subarray must be contiguous and you cannot reuse elements between different subarrays. That is, once you pick a subarray, the next subarray must start after the end of the previous one.

Return the maximum number of such non-overlapping subarrays.

Thought Process

At first glance, you might think of checking all possible subarrays and counting those whose sum equals target. However, this brute-force approach is inefficient for large arrays, as it would require checking every possible start and end index, resulting in a time complexity of O(n²).

To optimize, we can use the idea of prefix sums: by tracking the sum of elements up to each index, we can quickly determine if a subarray ending at the current index sums to target. To ensure non-overlapping subarrays, we need a way to "reset" our tracking each time we find a valid subarray, so that we don't count overlapping ones.

The key insight is to use a set to remember prefix sums, and whenever we find a valid subarray, we reset our tracking to prevent overlaps.

Solution Approach

• Prefix Sum Calculation: We maintain a running sum as we iterate through the array. This helps us quickly calculate the sum of any subarray ending at the current index.
• Hash Set for Seen Prefix Sums: We use a set to store all prefix sums seen so far. If at any point, prefix_sum - target exists in the set, it means there is a subarray ending at the current index whose sum is exactly target.
• Counting and Resetting: When we find such a subarray, we increment our count and reset both the prefix sum and the set. This ensures that the next subarray we find does not overlap with the previous one.
• Step-by-Step:
  1. Initialize count to 0, prefix_sum to 0, and seen to contain only 0 (to handle subarrays starting from index 0).
  2. For each number in nums:
     • Add the number to prefix_sum.
     • If prefix_sum - target is in seen:
       • Increment count.
       • Reset prefix_sum to 0 and seen to {0}.
     • Otherwise, add prefix_sum to seen.
  3. Return count at the end.

This approach ensures we only count non-overlapping subarrays and runs efficiently in linear time.

Example Walkthrough

Let's consider nums = [1, 1, 1, 1, 1] and target = 2.

• Start: prefix_sum = 0, seen = {0}, count = 0
• Index 0: Add 1 → prefix_sum = 1. 1-2 = -1 not in seen. Add 1 to seen.
• Index 1: Add 1 → prefix_sum = 2. 2-2 = 0 is in seen! Increment count = 1. Reset prefix_sum = 0, seen = {0}.
• Index 2: Add 1 → prefix_sum = 1. 1-2 = -1 not in seen. Add 1 to seen.
• Index 3: Add 1 → prefix_sum = 2. 2-2 = 0 is in seen! Increment count = 2. Reset prefix_sum = 0, seen = {0}.
• Index 4: Add 1 → prefix_sum = 1. 1-2 = -1 not in seen. Add 1 to seen.

Final answer: 2 non-overlapping subarrays with sum 2.

Time and Space Complexity

• Brute-force:
  • Time: O(n²) because you must check every possible subarray.
  • Space: O(1) extra space.
• Optimized (Prefix Sum + Set):
  • Time: O(n), since we go through the array once and set operations are O(1) on average.
  • Space: O(n) in the worst case, as the set of prefix sums can grow up to the size of the array before a reset.

Summary

The problem asks for the maximum number of non-overlapping subarrays that sum to a given target. By using prefix sums and a set to track seen sums, we can efficiently find these subarrays in linear time. Resetting our tracking after each valid subarray ensures non-overlapping, and the solution elegantly leverages hash-based lookups for speed. This approach is much more efficient and scalable than brute-force enumeration.