Maximum Number of Non-Overlapping Subarrays With Sum Equals Target - Problem

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.

A subarray is a contiguous part of an array. Two subarrays are non-overlapping if they do not share any common elements.

Input & Output

Example 1 — Basic Case

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

› Output: 2

💡 Note: We can form 2 non-overlapping subarrays: [1,1] (sum=2) and [1,1] (sum=2). The last element [1] cannot form another subarray with sum=2.

Example 2 — Single Elements

$ Input: nums = [-1,1,5,1,1], target = 1

› Output: 3

💡 Note: We can form 3 non-overlapping subarrays: [1], [1], and [1]. Each single element equals the target.

Example 3 — Mixed Values

$ Input: nums = [-1,-1,1,1,1], target = 0

› Output: 1

💡 Note: We can form 1 subarray: [-1,1] (sum=0). The remaining elements [-1,1,1] could form [-1,1] but we already used one -1.

Constraints

1 ≤ nums.length ≤ 10⁵
-10⁴ ≤ nums[i] ≤ 10⁴
0 ≤ target ≤ 10⁶

Visualization

Tap to expand

Asked in

G Google 12 a Amazon 8 M Microsoft 6

The key insight is to use a greedy approach with prefix sums. As soon as we find a subarray with sum equal to target, we take it and reset our search. This maximizes the number of non-overlapping subarrays. Best approach uses prefix sum with hash set in O(n) time and O(n) space.

Common Approaches

✓ Brute Force - Check All Subarrays

⏱️ Time: O(n² × 2ⁿ) Space: O(n)

Check every possible subarray to see if its sum equals target, then use backtracking to find the maximum number of non-overlapping subarrays that can be selected.

Greedy Approach with Prefix Sum

⏱️ Time: O(n) Space: O(n)

Traverse the array once while maintaining a running prefix sum. Use a hash set to track seen prefix sums. When we find a subarray with target sum, greedily take it and reset.

Brute Force - Check All Subarrays — Algorithm Steps

Generate all subarrays and their sums
Use backtracking to try all combinations
Track which indices are used to avoid overlap
Return maximum count found

Visualization

Tap to expand

Step-by-Step Walkthrough

Find Valid Subarrays

Check every subarray for target sum

Try Combinations

Use backtracking to find max non-overlapping set

Result

Return maximum count found

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

typedef struct {
    int start, end;
} Range;

int backtrack(Range* validSubarrays, int validCount, int index, bool* used, int n, int count) {
    if (index == validCount) {
        return count;
    }
    
    // Skip current subarray
    int result = backtrack(validSubarrays, validCount, index + 1, used, n, count);
    
    // Try to include current subarray if no overlap
    int start = validSubarrays[index].start;
    int end = validSubarrays[index].end;
    bool canUse = true;
    
    for (int i = start; i <= end; i++) {
        if (used[i]) {
            canUse = false;
            break;
        }
    }
    
    if (canUse) {
        bool* newUsed = (bool*)malloc(n * sizeof(bool));
        memcpy(newUsed, used, n * sizeof(bool));
        for (int i = start; i <= end; i++) {
            newUsed[i] = true;
        }
        int temp = backtrack(validSubarrays, validCount, index + 1, newUsed, n, count + 1);
        if (temp > result) result = temp;
        free(newUsed);
    }
    
    return result;
}

int solution(int* nums, int numsSize, int target) {
    Range validSubarrays[1000];
    int validCount = 0;
    
    // Find all subarrays with sum equal to target
    for (int i = 0; i < numsSize; i++) {
        int currentSum = 0;
        for (int j = i; j < numsSize; j++) {
            currentSum += nums[j];
            if (currentSum == target) {
                validSubarrays[validCount].start = i;
                validSubarrays[validCount].end = j;
                validCount++;
            }
        }
    }
    
    bool* used = (bool*)calloc(numsSize, sizeof(bool));
    int result = backtrack(validSubarrays, validCount, 0, used, numsSize, 0);
    free(used);
    return result;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int nums[100], numsSize = 0;
    char* token = strtok(line, "[],\n");
    while (token != NULL) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, "[],\n");
    }
    
    int target;
    scanf("%d", &target);
    
    int result = solution(nums, numsSize, target);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n² × 2ⁿ)

O(n²) to generate all subarrays, then O(2ⁿ) to try all combinations

⚠ Quadratic Growth

Space Complexity

O(n)

Recursion stack and tracking used indices

⚡ Linearithmic Space

25.4K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Maximum Number of Non-Overlapping Subarrays With Sum Equals Target - Problem

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Check All Subarrays — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler