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 <= 105-104 <= nums[i] <= 1040 <= target <= 106Problem Overview: You are given an integer array and a target value. The goal is to find the maximum number of non-overlapping subarrays whose sum equals the target. Once a valid subarray is chosen, its elements cannot be reused in another subarray, so the strategy must maximize count while preventing overlap.
Approach 1: Prefix Sum with HashMap (O(n) time, O(n) space)
This approach uses a running prefix sum and a hash map to quickly detect whether a previous prefix creates a subarray with sum equal to the target. As you iterate through the array, maintain the cumulative sum. If current_sum - target already exists in the hash map, a valid subarray ending at the current index is found. To enforce non-overlapping behavior, reset the prefix tracking after counting a valid subarray. This greedy reset ensures future subarrays start fresh and do not intersect with previously selected segments.
The hash map enables constant-time lookups for prior prefix sums. Each element is processed exactly once, so the time complexity is O(n) with O(n) auxiliary space in the worst case. This technique heavily relies on concepts from prefix sum and hash table lookups. It works for arrays containing positive, negative, or zero values where sliding window techniques typically fail.
Approach 2: Sliding Window with Set (O(n) time, O(n) space)
This variation tracks prefix sums inside a set while scanning the array. Maintain a running sum and check whether current_sum - target exists in the set. If it does, a valid subarray has been found. Increment the result counter and clear the set to restart the search from the next position, ensuring no overlap with previously counted subarrays.
The key idea is similar to the hash map approach but simplified: only the existence of prefix sums matters, not their indices. Clearing the set after each match enforces the greedy decision to lock in the earliest valid subarray. Each element contributes to at most one window expansion, leading to O(n) time complexity and O(n) space usage. This approach combines ideas from array traversal and greedy selection.
Recommended for interviews: The Prefix Sum with HashMap solution is what most interviewers expect. It demonstrates understanding of prefix sum transformations and efficient hash-based lookups. Showing the brute reasoning first—checking subarray sums—and then optimizing with prefix sums highlights strong problem-solving progression. The greedy reset step is the critical insight that prevents overlaps while maximizing the number of valid subarrays.
This approach involves calculating the prefix sum and using a hash map to find subarrays that sum up to the target. By using a hash map, one can verify if any prefix sum by subtracting the target has been encountered before. The process helps keep track of the last index where a potential subarray ends, ensuring non-overlapping subarrays.
The solution initializes a hash map with prefix sum 0 at position -1, which is useful for finding subarrays starting from the first element. As we iterate through the array, we compute the current sum continuously by adding the current number to it. The main idea is to check if (current_sum - target) has been seen before, i.e., between the start and the current point a valid subarray forms. If true, it checks for a valid non-overlapping condition using the last_end variable to update count and set the new endpoint. The hash map is updated with the latest position for the current prefix sum.
Python
JavaScript
Time Complexity: O(n), where n is the number of elements in the array, because we traverse the array once while performing constant time operations per element. Space Complexity: O(n) in the worst case for storing prefix sums.
Another approach leverages a sliding window technique combined with a set to track seen prefix sums which helps reduce the size of the window while maintaining non-overlapping constraints on subarrays.
This approach uses a set to store all different prefix sums encountered. If at any point the difference between the current sum and the target is in the set, it means a subarray with the target sum has been found, allowing us to reset the seen set and increment the count. Range checking enables ensuring the non-overlapping requirement is met by starting anew upon every successful match.
C++
Time Complexity: O(n). Space Complexity: O(n).
We traverse the array nums, using the method of prefix sum + hash table, to find subarrays with a sum of target. If found, we increment the answer by one, then we set the prefix sum to 0 and continue to traverse the array nums until the entire array is traversed.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the array nums.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Prefix Sum with HashMap | Time Complexity: O(n), where n is the number of elements in the array, because we traverse the array once while performing constant time operations per element. Space Complexity: O(n) in the worst case for storing prefix sums. |
| Sliding Window with Set | Time Complexity: O(n). Space Complexity: O(n). |
| Greedy + Prefix Sum + Hash Table | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Prefix Sum with HashMap | O(n) | O(n) | General case with positive and negative numbers. Most common interview solution. |
| Sliding Window with Set | O(n) | O(n) | When using greedy segmentation to immediately lock valid subarrays and restart scanning. |
1546. Maximum Number of Non-Overlapping Subarrays With Sum Equals Target | Leetcode Medium • Chhavi Bansal • 3,706 views views
Watch 9 more video solutions →Practice Maximum Number of Non-Overlapping Subarrays With Sum Equals Target with our built-in code editor and test cases.
Practice on FleetCode