Minimum Positive Sum Subarray - Practice Coding Problems

Minimum Positive Sum Subarray - Problem

You are given an integer array nums and two integers l and r.

Your task is to find the minimum sum of a subarray whose size is between l and r (inclusive) and whose sum is greater than 0.

Return the minimum sum of such a subarray. If no such subarray exists, return -1.

A subarray is a contiguous non-empty sequence of elements within an array.

Input & Output

Example 1 — Basic Case

$ Input: nums = [2,-3,4,-1,2], l = 2, r = 3

› Output: 1

💡 Note: Check all subarrays of length 2-3: [2,-3]=-1 (negative), [-3,4]=1 ✓, [4,-1]=3 ✓, [-1,2]=1 ✓, [2,-3,4]=3 ✓, [-3,4,-1]=0 (not positive), [4,-1,2]=5 ✓. Minimum positive sum is 1.

Example 2 — All Negative

$ Input: nums = [-2,-3,-1], l = 2, r = 3

› Output: -1

💡 Note: All possible subarrays have negative sums: [-2,-3]=-5, [-3,-1]=-4, [-1]=-1 (wrong length), [-2,-3,-1]=-6. No positive sum exists.

Example 3 — Single Positive Element

$ Input: nums = [-1,2,-3], l = 1, r = 2

› Output: 2

💡 Note: Valid subarrays: [-1]=-1, [2]=2 ✓, [-3]=-3, [-1,2]=1 ✓, [2,-3]=-1. Minimum positive sum is 1, but wait - l=1,r=2 means length 1-2, so [2]=2 is length 1 which is valid. Minimum is 1 from [-1,2].

Constraints

1 ≤ nums.length ≤ 10⁵
-10⁵ ≤ nums[i] ≤ 10⁵
1 ≤ l ≤ r ≤ nums.length

Visualization

Tap to expand

Understanding the Visualization

Input

Array with positive/negative numbers, length constraints l,r

Process

Check all subarrays of length l to r, find positive sums

Output

Return minimum positive sum, or -1 if none exists

Key Takeaway

🎯 Key Insight: Use prefix sums to efficiently calculate all subarray sums and track the minimum positive value

Asked in

G Google 15 a Amazon 12 M Microsoft 8 🍎 Apple 6

The key insight is to systematically check all subarrays of valid length (between l and r) and find the minimum positive sum. Best approach uses prefix sums to calculate subarray sums in O(1) time. Time: O(n²), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Optimized Sliding Window	O(n²)	O(n)	Use sliding window technique with prefix sums for better performance
Prefix Sum Optimization	O(n²)	O(n)	Use prefix sums to calculate subarray sums in O(1) time
Brute Force - Check All Subarrays	O(n³)	O(1)	Generate all possible subarrays of valid length and find minimum positive sum

Optimized Sliding Window — Algorithm Steps

Build prefix sum array
For each valid window size
Slide window across array using prefix sums
Track minimum positive sum across all windows

Visualization

Tap to expand

Step-by-Step Walkthrough

Window Size

Try each size from l to r

Slide Window

Move window across array

Track Minimum

Keep smallest positive sum

Code -

solution.c — C

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

int solution(int* nums, int numsSize, int l, int r) {
    // Build prefix sum array
    long long* prefix = (long long*)calloc(numsSize + 1, sizeof(long long));
    for (int i = 0; i < numsSize; i++) {
        prefix[i + 1] = prefix[i] + nums[i];
    }
    
    long long minSum = LLONG_MAX;
    
    // Try each valid window size
    for (int size = l; size <= r; size++) {
        // Slide window of this size across array
        for (int i = 0; i <= numsSize - size; i++) {
            // Calculate sum of window [i, i+size-1]
            long long windowSum = prefix[i + size] - prefix[i];
            
            // Update minimum if sum is positive
            if (windowSum > 0) {
                minSum = (windowSum < minSum) ? windowSum : minSum;
            }
        }
    }
    
    free(prefix);
    return minSum == LLONG_MAX ? -1 : (int)minSum;
}

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

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Outer loop for window sizes (r-l+1) × inner loop for positions (n)

⚠ Quadratic Growth

Space Complexity

O(n)

Prefix sum array of size n+1

⚡ Linearithmic Space

23.4K Views

Medium Frequency

~25 min Avg. Time

847 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

Optimized Sliding Window — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler