Jobs

Interviews

Discussions

Maximum Number of Non-Overlapping Subarrays With Sum Equals Target

Medium

Asked by:

7 views

Topics:

ArraysDynamic ProgrammingGreedy Algorithms

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 <= 10⁵
-10⁴ <= nums[i] <= 10⁴
0 <= target <= 10⁶

Try coding it in LeetCode

Maximum Number of Non-Overlapping Subarrays With Sum Equals Target

Medium

Asked by:

7 views

Topics:

ArraysDynamic ProgrammingGreedy Algorithms

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 <= 10⁵
-10⁴ <= nums[i] <= 10⁴
0 <= target <= 10⁶

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the possible ranges for the integers in the input array and for the target value? Can they be negative, zero, or only positive?
What should I return if no non-overlapping subarrays sum to the target? Should I return 0?
If there are multiple valid sets of non-overlapping subarrays that achieve the maximum count, is any one of them acceptable, or is there a specific criteria for selecting one?
Can the same element in the input array be part of multiple, non-overlapping subarrays that each sum to the target? (Clarifying the definition of 'non-overlapping' with respect to element reuse)
Is the input array guaranteed to be non-empty, or should I handle the case where the input array is null or empty?

Brute Force Solution

Approach

The goal is to find the most groups of numbers in a larger list that each add up to a specific number, where the groups don't overlap. The brute force approach involves checking every possible combination of groups to find the best one. This means trying every possible starting and ending point for each group.

Here's how the algorithm would work step-by-step:

Start by considering a single number as a potential group.
Check if that number equals the target. If it does, you have one valid group.
Next, consider the first two numbers as a potential group. Check if their sum equals the target.
Then, consider the first three numbers, and so on. Keep checking these sums until you've considered the entire initial sequence.
Repeat this process, starting with the second number in the list. Consider the second number alone, then the second and third, then the second, third, and fourth, and so on.
Continue this process, moving the starting point further down the list each time, until you've considered every possible starting point.
Each time you find a group that equals the target, remember it and how many groups you have so far.
But remember, groups can't overlap. So, once you have a valid group, skip over those numbers when trying to make the next group.
After considering every possible group and every possible combination of non-overlapping groups, select the combination that gives you the highest number of valid groups.

Code Implementation

def max_non_overlapping_subarrays(numbers, target):
    max_subarrays = 0
    list_length = len(numbers)

    for start_index in range(list_length):
        number_of_subarrays = 0
        current_index = start_index

        while current_index < list_length:
            current_sum = 0
            for end_index in range(current_index, list_length):
                current_sum += numbers[end_index]

                if current_sum == target:
                    number_of_subarrays += 1
                    # Skip over the current subarray since it cannot overlap.
                    current_index = end_index + 1
                    break
            else:
                #Advance if we can't find a matching target sum.
                current_index += 1

        max_subarrays = max(max_subarrays, number_of_subarrays)
        #Try all possible start points.

    return max_subarrays

Big(O) Analysis

Time Complexity

O(n³) – The brute force approach iterates through all possible subarrays. For an input array of size n, there are approximately n choices for the starting point of a subarray. For each starting point, there are approximately n choices for the ending point of the subarray. For each possible subarray, we need to compute its sum, which takes O(n) in the worst case. Therefore, the overall time complexity is approximately n * n * n, which simplifies to O(n³).

Space Complexity

O(1) – The provided brute force approach, as described, doesn't use any auxiliary data structures like arrays, hash maps, or recursion. It only iterates through the input list and maintains a few variables to track starting and ending indices of subarrays and the count of non-overlapping subarrays. Therefore, the space used remains constant irrespective of the size of the input list, resulting in O(1) space complexity.

Optimal Solution

Approach

The best way to find the most non-overlapping groups that add up to a target is to go through the data once and be greedy. The algorithm efficiently keeps track of the current sum and resets as soon as a valid group is found, ensuring no overlap.

Here's how the algorithm would work step-by-step:

Start at the beginning of the data.
Keep track of the running total as you move along.
If the running total equals the target value, then you have found a valid group.
Increase the count of non-overlapping groups you have found.
Reset the running total to zero and start looking for the next group from the next data point.
If you reach the end of the data, return the total count of non-overlapping groups you found.

Code Implementation

def maximum_non_overlapping_subarrays_with_sum_equals_target(numbers, target):
    count_of_non_overlapping_subarrays = 0
    current_running_sum = 0

    for number in numbers:
        current_running_sum += number

        # Check if the current running sum equals the target
        if current_running_sum == target:
            # Increment the count because we found a valid subarray
            count_of_non_overlapping_subarrays += 1

            # Reset the running sum to 0
            current_running_sum = 0

    # Return the final count of non-overlapping subarrays
    return count_of_non_overlapping_subarrays

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input array of size n only once. During this single pass, it maintains a running sum and checks if the sum equals the target. If it does, it increments the count and resets the running sum. Since each element is visited and processed exactly once, the time complexity is directly proportional to the size of the input array, resulting in O(n) time complexity.

Space Complexity

O(1) – The provided plain English explanation describes an iterative process that only requires storing the running total and the count of non-overlapping groups. These variables occupy a constant amount of space regardless of the input array's size, N. Therefore, no auxiliary data structures scale with the input size, resulting in constant auxiliary space complexity.

Edge Cases

Case	How to Handle
Empty input array	Return 0 if the input array is empty because no subarrays can be formed.
Array with a single element that equals the target	Return 1 if the array has one element and it equals the target.
Array with all zeros and target is zero	Return the number of subarrays in the array of all zeros if the target is zero since they all sum to zero.
Array with all the same negative numbers, target negative.	The solution should correctly identify non-overlapping subarrays where the sum equals the negative target, by ensuring sum == target and only resetting the prefix set after an occurrence.
Array with large numbers that could cause integer overflow	Consider using long data type to store prefix sums if integer overflow is possible with the input range.
No subarrays sum to the target.	The algorithm should return 0 if no subarray sums to the target, as indicated by no non-overlapping intervals being found.
Target is zero and array contains negative and positive numbers summing to zero	The solution must correctly count the non-overlapping subarrays summing to zero, restarting the prefix set after each successful interval.
Large array with many overlapping subarrays summing to target	The solution should efficiently iterate the array, using the hashmap prefix sum technique to check for the required prefixes with O(n) time complexity and resetting the prefix sum set to ensure intervals are non-overlapping.

Empty input array

How to Handle:

Return 0 if the input array is empty because no subarrays can be formed.

Array with a single element that equals the target

How to Handle:

Return 1 if the array has one element and it equals the target.

Array with all zeros and target is zero

How to Handle:

Return the number of subarrays in the array of all zeros if the target is zero since they all sum to zero.

Array with all the same negative numbers, target negative.

How to Handle:

The solution should correctly identify non-overlapping subarrays where the sum equals the negative target, by ensuring sum == target and only resetting the prefix set after an occurrence.

Array with large numbers that could cause integer overflow

How to Handle:

Consider using long data type to store prefix sums if integer overflow is possible with the input range.

No subarrays sum to the target.

How to Handle:

The algorithm should return 0 if no subarray sums to the target, as indicated by no non-overlapping intervals being found.

Target is zero and array contains negative and positive numbers summing to zero

How to Handle:

The solution must correctly count the non-overlapping subarrays summing to zero, restarting the prefix set after each successful interval.

Large array with many overlapping subarrays summing to target

How to Handle:

The solution should efficiently iterate the array, using the hashmap prefix sum technique to check for the required prefixes with O(n) time complexity and resetting the prefix sum set to ensure intervals are non-overlapping.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the possible ranges for the integers in the input array and for the target value? Can they be negative, zero, or only positive?
What should I return if no non-overlapping subarrays sum to the target? Should I return 0?
If there are multiple valid sets of non-overlapping subarrays that achieve the maximum count, is any one of them acceptable, or is there a specific criteria for selecting one?
Can the same element in the input array be part of multiple, non-overlapping subarrays that each sum to the target? (Clarifying the definition of 'non-overlapping' with respect to element reuse)
Is the input array guaranteed to be non-empty, or should I handle the case where the input array is null or empty?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start by considering a single number as a potential group.
Check if that number equals the target. If it does, you have one valid group.
Next, consider the first two numbers as a potential group. Check if their sum equals the target.
Then, consider the first three numbers, and so on. Keep checking these sums until you've considered the entire initial sequence.
Repeat this process, starting with the second number in the list. Consider the second number alone, then the second and third, then the second, third, and fourth, and so on.
Continue this process, moving the starting point further down the list each time, until you've considered every possible starting point.
Each time you find a group that equals the target, remember it and how many groups you have so far.
But remember, groups can't overlap. So, once you have a valid group, skip over those numbers when trying to make the next group.
After considering every possible group and every possible combination of non-overlapping groups, select the combination that gives you the highest number of valid groups.

Code Implementation

def max_non_overlapping_subarrays(numbers, target):
    max_subarrays = 0
    list_length = len(numbers)

    for start_index in range(list_length):
        number_of_subarrays = 0
        current_index = start_index

        while current_index < list_length:
            current_sum = 0
            for end_index in range(current_index, list_length):
                current_sum += numbers[end_index]

                if current_sum == target:
                    number_of_subarrays += 1
                    # Skip over the current subarray since it cannot overlap.
                    current_index = end_index + 1
                    break
            else:
                #Advance if we can't find a matching target sum.
                current_index += 1

        max_subarrays = max(max_subarrays, number_of_subarrays)
        #Try all possible start points.

    return max_subarrays

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Start at the beginning of the data.
Keep track of the running total as you move along.
If the running total equals the target value, then you have found a valid group.
Increase the count of non-overlapping groups you have found.
Reset the running total to zero and start looking for the next group from the next data point.
If you reach the end of the data, return the total count of non-overlapping groups you found.

Code Implementation

def maximum_non_overlapping_subarrays_with_sum_equals_target(numbers, target):
    count_of_non_overlapping_subarrays = 0
    current_running_sum = 0

    for number in numbers:
        current_running_sum += number

        # Check if the current running sum equals the target
        if current_running_sum == target:
            # Increment the count because we found a valid subarray
            count_of_non_overlapping_subarrays += 1

            # Reset the running sum to 0
            current_running_sum = 0

    # Return the final count of non-overlapping subarrays
    return count_of_non_overlapping_subarrays

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty input array	Return 0 if the input array is empty because no subarrays can be formed.
Array with a single element that equals the target	Return 1 if the array has one element and it equals the target.
Array with all zeros and target is zero	Return the number of subarrays in the array of all zeros if the target is zero since they all sum to zero.
Array with all the same negative numbers, target negative.	The solution should correctly identify non-overlapping subarrays where the sum equals the negative target, by ensuring sum == target and only resetting the prefix set after an occurrence.
Array with large numbers that could cause integer overflow	Consider using long data type to store prefix sums if integer overflow is possible with the input range.
No subarrays sum to the target.	The algorithm should return 0 if no subarray sums to the target, as indicated by no non-overlapping intervals being found.
Target is zero and array contains negative and positive numbers summing to zero	The solution must correctly count the non-overlapping subarrays summing to zero, restarting the prefix set after each successful interval.
Large array with many overlapping subarrays summing to target	The solution should efficiently iterate the array, using the hashmap prefix sum technique to check for the required prefixes with O(n) time complexity and resetting the prefix sum set to ensure intervals are non-overlapping.

Empty input array

How to Handle:

Return 0 if the input array is empty because no subarrays can be formed.

Array with a single element that equals the target

How to Handle:

Return 1 if the array has one element and it equals the target.

Array with all zeros and target is zero

How to Handle:

Return the number of subarrays in the array of all zeros if the target is zero since they all sum to zero.

Array with all the same negative numbers, target negative.

How to Handle:

The solution should correctly identify non-overlapping subarrays where the sum equals the negative target, by ensuring sum == target and only resetting the prefix set after an occurrence.

Array with large numbers that could cause integer overflow

How to Handle:

Consider using long data type to store prefix sums if integer overflow is possible with the input range.

No subarrays sum to the target.

How to Handle:

The algorithm should return 0 if no subarray sums to the target, as indicated by no non-overlapping intervals being found.

Target is zero and array contains negative and positive numbers summing to zero

How to Handle:

The solution must correctly count the non-overlapping subarrays summing to zero, restarting the prefix set after each successful interval.

Large array with many overlapping subarrays summing to target

How to Handle: