Minimum Positive Sum Subarray - Solution & Explanation

Problem Overview: You are given an integer array and two integers l and r. The task is to find the smallest positive sum of any subarray whose length is between l and r (inclusive). If no such subarray exists, return -1.

Approach 1: Brute Force Subarray Sum (O(n²) time, O(1) space)

The most direct solution is to enumerate every possible subarray and compute its sum. For each starting index, expand the subarray one element at a time and keep a running sum. Whenever the current length falls within the range [l, r], check if the sum is positive and update the minimum if needed. This approach relies on basic array iteration and works because every candidate subarray is evaluated explicitly. Time complexity is O(n²) in the worst case since each start index may expand up to n elements, while space usage stays O(1).

Approach 2: Sliding Window by Length (O(n * (r-l+1)) time, O(1) space)

A more structured solution uses the sliding window technique. Instead of recomputing sums repeatedly, iterate over every valid window size from l to r. For each size, compute the first window sum, then slide the window forward by subtracting the outgoing element and adding the incoming one. This keeps each window update O(1). Every time the window moves, check whether the sum is positive and update the global minimum. Internally this behaves similarly to a fixed-length window using incremental updates rather than recomputation.

This technique avoids repeatedly summing the same elements and makes the logic cleaner. The algorithm effectively processes all subarrays whose sizes fall in the allowed range while maintaining the running sum dynamically. The total work becomes O(n * (r-l+1)), which is significantly better than recomputing sums for each candidate window.

Another way to think about the computation is through prefix sums, where the sum of any subarray can be obtained using prefix[j] - prefix[i]. Sliding windows are essentially an optimized version of this idea when window sizes are fixed.

Recommended for interviews: Start by describing the brute force enumeration because it shows you understand the search space of subarrays. Then move to the sliding window optimization that maintains a running sum for each window size. Interviewers typically expect the optimized window-based approach since it avoids repeated summation and demonstrates familiarity with common array optimization patterns.