Maximum Number of Non-Overlapping Subarrays With Sum Equals Target

Problem

Given an array nums and an integer target, return the maximum number ofnon-empty non-overlapping subarrays such that the sum of values in each subarray is equal to target.

Examples

Example 1

Input: nums = [1,1,1,1,1], target = 2
Output: 2
Explanation: There are 2 non-overlapping subarrays [**1,1** ,1,**1,1**] with sum equals to target(2).

Example 2

Input: nums = [-1,3,5,1,4,2,-9], target = 6
Output: 2
Explanation: There are 3 subarrays with sum equal to 6.
([5,1], [4,2], [3,5,1,4,2,-9]) but only the first 2 are non-overlapping.

Constraints

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

Solution

Method 1 – Greedy + Prefix Sum + Hash Set

Intuition

To maximize the number of non-overlapping subarrays with sum equal to target, we can use a greedy approach: whenever we find a subarray ending at the current index with the required sum, we start a new search from the next index. We use a prefix sum and a hash set to efficiently check for such subarrays.

Approach

1. Initialize a set to store prefix sums, starting with 0.
2. Iterate through the array, maintaining a running sum.
3. If (current sum - target) is in the set, increment the answer and reset the set and sum for the next non-overlapping subarray.
4. Otherwise, add the current sum to the set and continue.
5. Return the total count of non-overlapping subarrays found.

Code

C++

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

Go

func maxNonOverlapping(nums []int, target int) int {
    seen := map[int]bool{0: true}
    ans, sum := 0, 0
    for _, x := range nums {
        sum += x
        if seen[sum-target] {
            ans++
            seen = map[int]bool{0: true}
            sum = 0
        } else {
            seen[sum] = true
        }
    }
    return ans
}

Java

import java.util.*;
class Solution {
    public int maxNonOverlapping(int[] nums, int target) {
        Set<Integer> seen = new HashSet<>();
        seen.add(0);
        int ans = 0, sum = 0;
        for (int x : nums) {
            sum += x;
            if (seen.contains(sum - target)) {
                ans++;
                seen.clear();
                seen.add(0);
                sum = 0;
            } else {
                seen.add(sum);
            }
        }
        return ans;
    }
}

Kotlin

class Solution {
    fun maxNonOverlapping(nums: IntArray, target: Int): Int {
        val seen = mutableSetOf(0)
        var ans = 0
        var sum = 0
        for (x in nums) {
            sum += x
            if ((sum - target) in seen) {
                ans++
                seen.clear()
                seen.add(0)
                sum = 0
            } else {
                seen.add(sum)
            }
        }
        return ans
    }
}

Python

class Solution:
    def maxNonOverlapping(self, nums: list[int], target: int) -> int:
        seen = {0}
        ans = 0
        s = 0
        for x in nums:
            s += x
            if s - target in seen:
                ans += 1
                seen = {0}
                s = 0
            else:
                seen.add(s)
        return ans

Rust

use std::collections::HashSet;
impl Solution {
    pub fn max_non_overlapping(nums: Vec<i32>, target: i32) -> i32 {
        let mut seen = HashSet::new();
        seen.insert(0);
        let mut ans = 0;
        let mut sum = 0;
        for x in nums {
            sum += x;
            if seen.contains(&(sum - target)) {
                ans += 1;
                seen.clear();
                seen.insert(0);
                sum = 0;
            } else {
                seen.insert(sum);
            }
        }
        ans
    }
}

TypeScript

class Solution {
    maxNonOverlapping(nums: number[], target: number): number {
        let seen = new Set<number>([0]);
        let ans = 0, sum = 0;
        for (const x of nums) {
            sum += x;
            if (seen.has(sum - target)) {
                ans++;
                seen = new Set([0]);
                sum = 0;
            } else {
                seen.add(sum);
            }
        }
        return ans;
    }
}

Complexity

• ⏰ Time complexity: O(n), where n is the length of nums, since each element is processed once.
• 🧺 Space complexity: O(n), for the hash set of prefix sums.