Maximum Number of Non-Overlapping Subarrays With Sum Equals Target - Video Solutions

Problem 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.