Skip to main content
Talentd

Maximum Number of Non-Overlapping Subarrays With Sum Equals Target - Solution & Explanation

MediumArrayHash TableGreedyPrefix Sum9 min readAsked at: Google
Practice this problem

Problem Statement

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] <= 104
  • 0 <= target <= 106

Approach Overview

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.

Approach 1: Prefix Sum with HashMap

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.

Code

PythonJavaScript

Python

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 2: Sliding Window with Set

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.

Code

C++

C++

Complexity

Time Complexity: O(n). Space Complexity: O(n).

Try this approach in the editor →

Approach 3: Greedy + Prefix Sum + Hash Table

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Prefix Sum with HashMapO(n)O(n)General case with positive and negative numbers. Most common interview solution.
Sliding Window with SetO(n)O(n)When using greedy segmentation to immediately lock valid subarrays and restart scanning.

Video Solution

1546. Maximum Number of Non-Overlapping Subarrays With Sum Equals Target | Leetcode Medium • Chhavi Bansal • 3,765 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Maximum Number of Non-Overlapping Subarrays With Sum Equals Target easy or hard?
The problem is rated Medium on LeetCode with an acceptance rate around 48%. The challenge lies in recognizing the prefix sum pattern and applying a greedy reset to prevent overlapping subarrays.
Maximum Number of Non-Overlapping Subarrays With Sum Equals Target Python/Java solution
Python and JavaScript implementations typically use a hash map or set with prefix sums to detect valid subarrays in O(n) time. C++ solutions often follow the same logic using unordered_set or unordered_map while resetting state whenever a valid subarray is found.
How to solve Maximum Number of Non-Overlapping Subarrays With Sum Equals Target in O(n)?
Maintain a running prefix sum and store previously seen sums in a hash map or set. At each element, check whether current_sum minus target exists. When a match appears, increment the answer and reset the prefix tracking so the next subarray starts after the current one. This guarantees non-overlapping segments while keeping the algorithm linear.
What is the best approach for Maximum Number of Non-Overlapping Subarrays With Sum Equals Target?
The most efficient approach uses prefix sum with a hash map. Track the cumulative sum while iterating and check if current_sum minus target has appeared before. When found, increment the count and reset the prefix tracking to avoid overlap. This method runs in O(n) time with O(n) space.
Is Maximum Number of Non-Overlapping Subarrays With Sum Equals Target asked at Google/Amazon/Meta?
Problems involving prefix sums and non-overlapping subarrays frequently appear in interviews at companies like Amazon, Google, and Meta. Variations of this problem test understanding of prefix sums, greedy segmentation, and hash-based lookups.
What data structure is used in Maximum Number of Non-Overlapping Subarrays With Sum Equals Target?
The key data structures are a hash map or hash set to store prefix sums encountered during traversal. These structures allow constant-time checks for whether a previous prefix creates a subarray equal to the target.
What is the time complexity of Maximum Number of Non-Overlapping Subarrays With Sum Equals Target?
The optimal solutions run in O(n) time because the array is scanned once while maintaining prefix sums in a hash map or set. Each lookup and insertion is O(1) on average. Space complexity is O(n) due to storing prefix sums.

Ready to solve this problem?

Practice Maximum Number of Non-Overlapping Subarrays With Sum Equals Target with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays