#3364

Easy

auto_awesomeSliding window with running state updates

LeetCode Problem Workspace

Minimum Positive Sum Subarray

Find the minimum sum of any subarray of size between l and r with a positive total using efficient sliding window logic.

array sliding window prefix sum

Problem Statement

Given an integer array nums and two integers l and r, find the minimum sum of a contiguous subarray whose length is at least l and at most r and whose sum is strictly greater than zero.

Return the minimum positive sum found. If no such subarray exists, return -1. A subarray is a continuous sequence of elements from nums.

Examples

Example 1

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

Output: 1

The subarrays of length between l = 2 and r = 3 where the sum is greater than 0 are: Out of these, the subarray [3, -2] has a sum of 1, which is the smallest positive sum. Hence, the answer is 1.

Example 2

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

Output: -1

There is no subarray of length between l and r that has a sum greater than 0. So, the answer is -1.

Example 3

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

Output: 3

The subarray [1, 2] has a length of 2 and the minimum sum greater than 0. So, the answer is 3.

Constraints

1 <= nums.length <= 100
1 <= l <= r <= nums.length
-1000 <= nums[i] <= 1000

Solution Approach

Brute-force Sliding Window Check

Iterate over all possible starting indices and all valid lengths from l to r, compute the sum for each subarray, and track the minimum positive sum. This works due to small constraints, but summing each subarray naively can be slow for larger inputs.

Prefix Sum Optimization

Compute a prefix sum array to calculate any subarray sum in constant time. For each start index, calculate sums for lengths l to r quickly and update the minimum positive sum. This reduces repeated summation and ensures correctness for arrays with negative values.

Sliding Window with Running Updates

Maintain a running sum for a window starting at each index. Expand the window up to length r while checking sums of length at least l. Update the minimum positive sum as you move the window. This is the most direct approach for the given constraints and fits the sliding window pattern exactly.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n*r) in the worst case, iterating over each start index and length up to r. Space complexity is O(n) if using prefix sums or O(1) with a purely running sum approach.

What Interviewers Usually Probe

Check if the candidate recognizes that naive nested loops are sufficient due to constraints.
Listen for understanding of sliding window vs prefix sum trade-offs.
See if the candidate considers negative numbers affecting positive sum checks.

Common Pitfalls or Variants

Common pitfalls

Assuming all subarrays have positive sums and not checking for -1 return.
Incorrectly handling subarrays shorter than l or longer than r.
Recomputing sums from scratch instead of using running sums or prefix sums.

Follow-up variants

Find maximum positive sum subarray within a length range instead of minimum.
Return the actual subarray with minimum positive sum rather than just the sum.
Apply the same approach to a circular array, adjusting sliding window logic.

FAQ

What is the key pattern for solving Minimum Positive Sum Subarray?

The key pattern is sliding window with running sum updates, checking all subarrays of length between l and r efficiently.

Can I use a prefix sum array to optimize this problem?

Yes, prefix sums allow constant-time computation of subarray sums, which is efficient when iterating over all valid subarray lengths.

What should I return if no subarray has a positive sum?

Return -1, as specified in the problem, ensuring the solution handles negative-heavy arrays correctly.

Does the solution handle arrays with all negative numbers?

Yes, the sliding window or prefix sum approach correctly identifies that no positive sum exists and returns -1.

Is the sliding window approach always faster than brute-force here?

For small constraints, brute-force is acceptable, but sliding window reduces repeated summation and aligns with the intended pattern.

terminal

Solution

Solution 1: Enumeration

We can enumerate the left endpoint $i$ of the subarray, then enumerate the right endpoint $j$ from $i$ to $n$ within the interval $[i, n)$. We calculate the sum $s$ of the interval $[i, j]$. If $s$ is greater than $0$ and the interval length is between $[l, r]$, we update the answer.

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def minimumSumSubarray(self, nums: List[int], l: int, r: int) -> int:
        n = len(nums)
        ans = inf
        for i in range(n):
            s = 0
            for j in range(i, n):
                s += nums[j]
                if l <= j - i + 1 <= r and s > 0:
                    ans = min(ans, s)
        return -1 if ans == inf else ans

Continue Practicing

#3347 maximum frequency of an element after performing operations ii #3346 maximum frequency of an element after performing operations i #3413 maximum coins from k consecutive bags