1649. Maximum Number Of Non Overlapping Subarrays With Sum Equals Target¶

Difficulty: Medium

1649. Maximum Number of Non-Overlapping Subarrays With Sum Equals Target

Medium

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

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⁵
-10⁴ <= nums[i] <= 10⁴
0 <= target <= 10⁶

Solution¶

class Solution {
    public int maxNonOverlapping(int[] nums, int target) {
        int n = nums.length;
        HashMap<Integer, Integer> map = new HashMap<>();
        int prefSum = 0, count = 0;
        for (int i = 0; i < n; i++) {
            prefSum += nums[i];
            if (prefSum == target) {
                count++;
                prefSum = 0;
                map.clear();
            }
            else {
                int req = prefSum - target;
                if (map.containsKey(req)) {
                    count++;
                    prefSum = 0;
                    map.clear();
                }
                else {
                    if (!map.containsKey(prefSum)) 
                        map.put(prefSum, i);
                }
            } 
        }       
        return count; 
    }
}

Complexity Analysis¶

Time Complexity: O(?)
Space Complexity: O(?)

Approach¶

Detailed explanation of the approach will be added here