Maximum Number of Non-Overlapping Subarrays With Sum Equals Target

medium prefix sum hash table greedy

Problem

Given an array nums and an integer target, return the maximum number of non-empty, non-overlapping subarrays such that the sum of each subarray equals target. Two subarrays are non-overlapping when they share no index.

Inputnums = [1,1,1,1,1], target = 2

Output2

Pick [1,1] at indices 0–1 and [1,1] at indices 3–4, each summing to 2. They don't overlap, so the answer is 2.

nums (comma-separated)

target

def maxNonOverlapping(nums, target):
    seen = {0}          # prefix sums seen since the last cut
    prefix = 0          # running prefix sum within the current block
    count = 0
    for x in nums:
        prefix += x
        if prefix - target in seen:
            # a subarray ending here sums to target -> take it greedily
            count += 1
            seen = {0}   # cut: start a fresh block after this index
            prefix = 0
        else:
            seen.add(prefix)
    return count

function maxNonOverlapping(nums, target) {
  const seen = new Set([0]); // prefix sums since the last cut
  let prefix = 0;            // running prefix within the current block
  let count = 0;
  for (const x of nums) {
    prefix += x;
    if (seen.has(prefix - target)) {
      // subarray ending here sums to target -> take it greedily
      count++;
      seen.clear();
      seen.add(0);           // cut: fresh block after this index
      prefix = 0;
    } else {
      seen.add(prefix);
    }
  }
  return count;
}

int maxNonOverlapping(int[] nums, int target) {
    Set<Integer> seen = new HashSet<>();
    seen.add(0);            // prefix sums since the last cut
    int prefix = 0;        // running prefix within the current block
    int count = 0;
    for (int x : nums) {
        prefix += x;
        if (seen.contains(prefix - target)) {
            // subarray ending here sums to target -> take greedily
            count++;
            seen.clear();
            seen.add(0);   // cut: fresh block after this index
            prefix = 0;
        } else {
            seen.add(prefix);
        }
    }
    return count;
}

int maxNonOverlapping(vector<int>& nums, int target) {
    unordered_set<int> seen{0}; // prefix sums since the last cut
    int prefix = 0;            // running prefix within the block
    int count = 0;
    for (int x : nums) {
        prefix += x;
        if (seen.count(prefix - target)) {
            // subarray ending here sums to target -> take greedily
            count++;
            seen.clear();
            seen.insert(0);    // cut: fresh block after this index
            prefix = 0;
        } else {
            seen.insert(prefix);
        }
    }
    return count;
}

Explanation

A subarray nums[i..j] sums to target exactly when prefix[j] − prefix[i−1] = target, i.e. prefix[i−1] = prefix[j] − target. So as we scan and keep a running prefix, the question "does some subarray ending here sum to target?" becomes "have we seen the value prefix − target before?" — a single hash-set lookup.

We store every prefix sum we've encountered in the set seen, pre-loaded with 0 to allow a subarray that starts at index 0. When prefix − target is in seen, we have found a valid subarray that ends at the current index.

The key insight is greedy: as soon as a valid subarray ends, take it and never look back. Ending a subarray as early as possible leaves the most room for future subarrays, and it can be proven this never costs us a better answer. To enforce non-overlap we cut: clear seen back to {0} and reset prefix to 0, so later subarrays can only use indices after this cut.

Example: nums = [1,1,1,1,1], target = 2. Prefixes 1, 2 — at index 1 we see prefix − target = 0 in the set, so take [1,1] and cut. We restart, hit prefix 1, 2 again at index 3, take the second [1,1]. Result: 2.

Example: nums = [-1,3,5,1,4,2,-9], target = 6. The greedy cut grabs [5,1] then [4,2] before any larger overlapping window can form, giving 2.

Time: O(n) Space: O(n)