#1546

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Maximum Number of Non-Overlapping Subarrays With Sum Equals Target

Find the maximum number of non-overlapping subarrays that sum to a given target using efficient scanning and hash lookup.

array hash table greedy prefix sum

Problem Statement

Given an array of integers nums and an integer target, return the maximum number of non-empty, non-overlapping subarrays where the sum of elements in each subarray equals the target.

For example, given the input array nums = [1,1,1,1,1] and target = 2, you can form two non-overlapping subarrays that each sum to 2: [1, 1] and [1, 1].

Examples

Example 1

Input: nums = [1,1,1,1,1], target = 2

Output: 2

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

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

Solution Approach

Array Scanning with Prefix Sum

Iterate through the array while maintaining a running sum of elements. Whenever the running sum reaches the target, count this subarray and reset the sum to zero to ensure non-overlapping subarrays.

Hash Lookup for Efficient Sum Check

Use a hash map to store the prefix sums encountered as you scan the array. This allows for quick lookups to check if a subarray can form the target sum at each step.

Greedy Subarray Selection

Select subarrays greedily by resetting the sum after finding each valid subarray. This guarantees that subarrays do not overlap, and it maximizes the number of valid subarrays.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity is O(n) since we scan the array once and use hash map lookups for each element. The space complexity is O(n) for storing the prefix sums in the hash map.

What Interviewers Usually Probe

The candidate should demonstrate knowledge of prefix sum techniques.
The candidate should explain how to handle overlap prevention efficiently.
The candidate should show awareness of optimizing both time and space complexity.

Common Pitfalls or Variants

Common pitfalls

Forgetting to reset the sum after finding a valid subarray, leading to overlaps.
Using a brute-force approach with nested loops instead of efficient scanning.
Incorrectly handling negative numbers or non-zero target sums.

Follow-up variants

What if the array contains negative numbers? Can the approach still work?
How would you adapt the solution if there were multiple possible target sums?
What if the sum of the subarray needs to be greater than or less than the target?

FAQ

How do I find the maximum number of non-overlapping subarrays with a given sum?

You can solve this problem using array scanning and prefix sum techniques. By using a hash map to track prefix sums, you can efficiently check for subarrays that sum to the target and prevent overlap.

What is the time complexity of the optimal solution?

The optimal solution runs in O(n) time, as it only requires a single pass through the array and hash lookups for each element.

What are some common mistakes when solving this problem?

Common mistakes include not resetting the sum after finding a valid subarray, using inefficient brute-force solutions, and incorrectly handling negative numbers or non-zero targets.

Can the algorithm handle negative numbers in the array?

Yes, the algorithm works with negative numbers as well. It still relies on prefix sums, and hash lookup ensures correct identification of subarrays.

What does the greedy approach refer to in this problem?

The greedy approach refers to selecting subarrays as soon as their sum equals the target and then resetting the sum to prevent overlap. This maximizes the number of non-overlapping subarrays.

terminal

Solution

Solution 1: 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.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        ans = 0
        i, n = 0, len(nums)
        while i < n:
            s = 0
            vis = {0}
            while i < n:
                s += nums[i]
                if s - target in vis:
                    ans += 1
                    break
                i += 1
                vis.add(s)
            i += 1
        return ans

Continue Practicing

#1488 avoid flood in the city #1481 least number of unique integers after k removals #1442 count triplets that can form two arrays of equal xor