Maximize Non-Overlapping Subarrays with Target Sum – LeetCode 1546 Explained

Problem

LeetCode 1546 asks for the maximum number of non‑empty, non‑overlapping subarrays whose sum equals a given target.

Examples

Input: nums = [1,1,1,1,1], target = 2 Output: 2 Explanation: Two non‑overlapping subarrays [1,1] and [1,1] sum to 2.

Input: nums = [-1,3,5,1,4,2,-9], target = 6 Output: 2 Explanation: Three subarrays sum to 6, but only two are non‑overlapping.

Constraints

1 ≤ nums.length ≤ 10^5

-10^4 ≤ nums[i] ≤ 10^4

0 ≤ target ≤ 10^6

Analysis

Because the array may contain negative numbers, a sliding window cannot be used. Instead, we employ a prefix‑sum map to locate subarrays whose sum equals the target. After finding a valid subarray we record its ending index to ensure the next subarray starts after it.

When checking a candidate, we compare its start index with the last selected subarray’s end index; using “≥” is correct because the start index is treated as an open interval.

Solution (Java)

public int maxNonOverlapping(int[] nums, int target) {
    int ans = 0, last = -1, preSum = 0;
    Map<Integer, Integer> mp = new HashMap<>();
    mp.put(0, -1);
    for (int i = 0; i < nums.length; i++) {
        preSum += nums[i];
        Integer start = mp.get(preSum - target);
        if (start != null && start >= last) {
            ans++;
            last = i;
        }
        mp.put(preSum, i);
    }
    return ans;
}

Solution (C++)

int maxNonOverlapping(vector<int>& nums, int target) {
    int ans = 0, last = -1, preSum = 0;
    unordered_map<int, int> mp;
    mp[0] = -1;
    for (int i = 0; i < nums.size(); i++) {
        preSum += nums[i];
        auto it = mp.find(preSum - target);
        if (it != mp.end() && it->second >= last) {
            ++ans;
            last = i;
        }
        mp[preSum] = i;
    }
    return ans;
}