Maximum Number of Non-Overlapping Subarrays With Sum Equals Target

Medium
1852.

Maximum Number of Non-Overlapping Subarrays With Sum Equals Target

Maximum Number of Non-Overlapping Subarrays With Sum Equals Target is a medium coding problem on arrays, hash table and greedy, asked in Amazon and Google interviews.

Given an array nums and an integer target, choose as many non-empty, non-overlapping subarrays as possible such that every chosen subarray sums to exactly target. Two subarrays overlap if they share an index.

Return the maximum number of subarrays you can choose.

Example 1

Input
nums = [1,1,1,1,1], target = 2
Output
2
Explanation
[1,1] at indices 0–1 and [1,1] at indices 2–3 (or 3–4).

Example 2

Input
nums = [-1,3,5,1,4,2,-9], target = 6
Output
2
Explanation
Subarrays summing to 6: [5,1], [4,2] and [3,5,1,4,2,-9]. The first two do not overlap.

Example 3

Input
nums = [0,0,0], target = 0
Output
3
Explanation
Each single 0 is its own subarray.

Constraints

  • 1 <= nums.length <= 10^5
  • -10^4 <= nums[i] <= 10^4
  • 0 <= target <= 10^6
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var maxNonOverlapping = function(nums, target) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Maximum Number of Non-Overlapping Subarrays With Sum Equals Target

Maximum Number of Non-Overlapping Subarrays With Sum Equals Target solution: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Maximum Number of Non-Overlapping Subarrays With Sum Equals Target is a medium coding problem on arrays, hash table and greedy, asked in Amazon and Google interviews.

  • Difficulty: Medium
  • Topics: Arrays, Hash Table, Greedy, Prefix Sum
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Given an array nums and an integer target, choose as many non-empty, non-overlapping subarrays as possible such that every chosen subarray sums to exactly target. Two subarrays overlap if they share an index.

Return the maximum number of subarrays you can choose.

Example 1

Input: nums = [1,1,1,1,1], target = 2
Output: 2
Explanation: [1,1] at indices 0–1 and [1,1] at indices 2–3 (or 3–4).

Example 2

Input: nums = [-1,3,5,1,4,2,-9], target = 6
Output: 2
Explanation: Subarrays summing to 6: [5,1], [4,2] and [3,5,1,4,2,-9]. The first two do not overlap.

Example 3

Input: nums = [0,0,0], target = 0
Output: 3
Explanation: Each single 0 is its own subarray.

Constraints

  • 1 <= nums.length <= 10^5
  • -10^4 <= nums[i] <= 10^4
  • 0 <= target <= 10^6

Hints for Maximum Number of Non-Overlapping Subarrays With Sum Equals Target

  1. Hint 1

    Think greedily: among all valid subarrays, which one would you want to pick first?

  2. Hint 2

    Picking the valid subarray that ends earliest never hurts — it leaves the most room for the rest.

  3. Hint 3

    Scan with prefix sums and a set of the prefix sums seen since the last chosen subarray ended. When prefix - target is in the set, a subarray ends here: count it and clear the set (start fresh from this point).

How to solve Maximum Number of Non-Overlapping Subarrays With Sum Equals Target

This is interval scheduling: the subarrays summing to target are intervals, and the classic greedy — always take the one that ends first — maximises the count. Prefix sums with a hash set find, at every index, whether some valid subarray that starts after the last chosen one ends here.

Approach

  1. Keep seen = {0}, prefix = 0, count = 0.
  2. For each element, add it to prefix.
  3. If prefix - target is in seen, a valid subarray ends here: count += 1, then reset seen = {0} and prefix = 0 so later subarrays start after this index.
  4. Otherwise add prefix to seen. Return count.

Why it works

Exchange argument: in any optimal selection, replace its first subarray by the valid subarray with the earliest end; it still ends no later, so it overlaps nothing else in the selection. Repeating on the remainder of the array yields the greedy choice at every step. The set holds exactly the prefix sums of the positions after the last chosen subarray, so prefix - target in the set means a valid subarray starting after that point ends at the current index — and the first such index is the earliest end.

Complexity

  • Time — O(n)
  • Space — O(n)

Pitfalls

  • Reset the set to contain 0 (the empty prefix of the new segment), not to empty — otherwise a subarray that starts right after the previous one is missed.
  • Negative numbers rule out a sliding window; prefix sums with a hash set are needed.
  • target = 0 with zeros: each zero alone counts, which the reset handles.

Reference solution

Python

from typing import List

def maxNonOverlapping(nums: List[int], target: int) -> int:
    seen = {0}
    prefix = 0
    count = 0
    for x in nums:
        prefix += x
        if prefix - target in seen:
            count += 1
            seen = {0}
            prefix = 0
        else:
            seen.add(prefix)
    return count

Java

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

C++

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

JavaScript

var maxNonOverlapping = function(nums, target) {
    var seen = new Set([0]);
    var prefix = 0, count = 0;
    for (var i = 0; i < nums.length; i++) {
        prefix += nums[i];
        if (seen.has(prefix - target)) {
            count++;
            seen = new Set([0]);
            prefix = 0;
        } else {
            seen.add(prefix);
        }
    }
    return count;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets