Find Two Non-overlapping Sub-arrays Each With Target Sum

Find Two Non-overlapping Sub-arrays Each With Target Sum - Problem

You are given an array of integers arr and an integer target.

You have to find two non-overlapping sub-arrays of arr each with a sum equal to target. There can be multiple answers so you have to find an answer where the sum of the lengths of the two sub-arrays is minimum.

Return the minimum sum of the lengths of the two required sub-arrays, or return -1 if you cannot find such two sub-arrays.

Input & Output

Example 1 — Basic Case

$ Input: arr = [3,2,2,4,3], target = 3

› Output: 2

💡 Note: Only sub-arrays with sum 3 are [3] at index 0 and [3] at index 4. Total length = 1 + 1 = 2.

Example 2 — Multiple Options

$ Input: arr = [7,3,4,7], target = 7

› Output: 2

💡 Note: Sub-arrays with sum 7: [7] at index 0 (length 1), [3,4] at indices 1-2 (length 2), [7] at index 3 (length 1). Best pair: [7] + [7] = 1 + 1 = 2.

Example 3 — No Solution

$ Input: arr = [1,1,1,1], target = 3

› Output: -1

💡 Note: Sub-arrays with sum 3: [1,1,1] at indices 0-2 and [1,1,1] at indices 1-3. These overlap, so no valid pair exists.

Constraints

1 ≤ arr.length ≤ 1000
1 ≤ arr[i] ≤ 1000
1 ≤ target ≤ 300

Visualization

Tap to expand

Understanding the Visualization

Input Analysis

Array [3,2,2,4,3] with target sum 3

Find Valid Sub-arrays

Identify all sub-arrays that sum to target: [3] at index 0, [3] at index 4

Check Non-overlapping

Verify the sub-arrays don't share any indices and return minimum total length

Key Takeaway

🎯 Key Insight: Use sliding window with prefix tracking to efficiently find valid sub-arrays while maintaining information about the best previous options for optimal pairing.

Asked in

G Google 45 a Amazon 38 M Microsoft 32 f Facebook 28

The key insight is to use sliding window technique combined with dynamic programming to efficiently find valid sub-arrays and track the best non-overlapping combinations. The optimal approach uses sliding window with prefix tracking to achieve O(n) time complexity by maintaining information about the shortest sub-array found before each position.

Common Approaches

Approach	Time	Space	Notes
✓ Dynamic Programming Approach	O(n²)	O(n)	Use DP to track optimal solutions for each position
Sliding Window with Prefix Tracking	O(n)	O(n)	Use sliding window to find sub-arrays and track the best prefix option
Brute Force - Check All Pairs	O(n⁴)	O(n²)	Generate all possible sub-arrays and check every non-overlapping pair

Dynamic Programming Approach — Algorithm Steps

Find all valid sub-arrays with their positions and lengths
Use DP to track minimum length achievable ending at each position
Combine current sub-array with best non-overlapping previous result

Visualization

Tap to expand

Step-by-Step Walkthrough

Find All Valid

Identify all sub-arrays that sum to target

Build DP Table

Track minimum length achievable at each position

Combine Results

For each sub-array, check if it can pair with previous optimal

Code -

solution.c — C

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

int min(int a, int b) {
    return a < b ? a : b;
}

int solution(int* arr, int arrSize, int target) {
    int validSubarrays[1000][3];
    int validCount = 0;
    
    for (int i = 0; i < arrSize; i++) {
        int currentSum = 0;
        for (int j = i; j < arrSize; j++) {
            currentSum += arr[j];
            if (currentSum == target) {
                validSubarrays[validCount][0] = i;
                validSubarrays[validCount][1] = j;
                validSubarrays[validCount][2] = j - i + 1;
                validCount++;
            }
        }
    }
    
    if (validCount < 2) return -1;
    
    int* minLen = (int*)malloc(arrSize * sizeof(int));
    for (int i = 0; i < arrSize; i++) {
        minLen[i] = INT_MAX;
    }
    int result = INT_MAX;
    
    for (int k = 0; k < validCount; k++) {
        int start = validSubarrays[k][0];
        int end = validSubarrays[k][1];
        int length = validSubarrays[k][2];
        
        if (start > 0 && minLen[start - 1] != INT_MAX) {
            result = min(result, length + minLen[start - 1]);
        }
        
        for (int i = end; i < arrSize; i++) {
            minLen[i] = min(minLen[i], length);
            if (i > 0) {
                minLen[i] = min(minLen[i], minLen[i - 1]);
            }
        }
    }
    
    free(minLen);
    return result == INT_MAX ? -1 : result;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int arr[1000];
    int arrSize = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] != ' ' && token[0] != '\n') {
            arr[arrSize++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    int target;
    scanf("%d", &target);
    
    int result = solution(arr, arrSize, target);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

O(n²) to find all sub-arrays, O(n) to process DP

⚠ Quadratic Growth

Space Complexity

O(n)

DP array and storage for valid sub-arrays

⚡ Linearithmic Space

24.5K Views

Medium Frequency

~25 min Avg. Time

890 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

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Dynamic Programming Approach — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler