We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Number of Non-Overlapping Subarrays With Sum Equals Target

Number: 1649

Difficulty: Medium

Paid? No

Companies: Google

Problem Description

Given an array of integers nums and an integer target, find the maximum number of non-empty, non-overlapping subarrays such that the sum of each subarray equals target.

Key Insights

  • A greedy strategy is optimal: once you find a valid subarray, you “cut” the array and search for the next non-overlapping group.
  • The use of prefix sums allows you to quickly detect if a subarray sum equals target.
  • A hash set (or hash table) is used to store previously seen prefix sums within the current segment to efficiently check if (current sum - target) has appeared.
  • When a valid subarray is encountered, reset the running sum and the hash set to guarantee no overlap.

Space and Time Complexity

Time Complexity: O(n) – The solution makes one pass through the array. Space Complexity: O(n) – In the worst-case scenario, the hash set could store all intermediate prefix sums (though it is reset upon finding a valid subarray).

Solution

The solution iterates through nums, computing a cumulative sum. Along the way, it stores each cumulative sum in a hash set (initially containing 0) representing the prefix sums within the current segment. At each index, check if (cumulative sum - target) exists in the set. If it does, a valid subarray ending at the current index is found; increment the count and reset both the cumulative sum and the hash set to ensure subsequent subarrays do not overlap the found subarray.

Key points:

  • The hash set helps in dealing with arrays that contain negative numbers as well as positive numbers.
  • Resetting when a valid subarray is found ensures that the next search starts afresh to avoid overlapping with the already counted subarray.
  • This algorithm is greedy: it always takes the earliest valid subarray, which maximizes the total count.

Code Solutions

# Python solution for Maximum Number of Non-Overlapping Subarrays With Sum Equals Target
def maxNonOverlapping(nums, target):
    count = 0         # To count valid subarrays
    curr_sum = 0      # Cumulative sum for the current segment
    prefix_set = {0}  # Set to store prefix sums; start with 0 to handle subarray from index 0

    for num in nums:
        curr_sum += num
        # If the difference between current sum and target exists in the set,
        # it means that a subarray summing to target is found.
        if curr_sum - target in prefix_set:
            count += 1
            # Reset for the next non-overlapping segment
            curr_sum = 0
            prefix_set = {0}
        else:
            prefix_set.add(curr_sum)
    return count

# Example usage:
# print(maxNonOverlapping([1,1,1,1,1], 2))  # Expected output: 2
← Back to All Questions