3364. Minimum Positive Sum Subarray
- Array
- Sliding Window
- Prefix Sum
Intuition
With prefix sums P, the subarray nums[i..j-1] sums to P[j] - P[i], and its length is j - i. Fix the end j. The length constraint l <= j - i <= r means the start i must lie in [j - r, j - l], and that range slides right by one as j grows.
For a fixed j, the sum P[j] - P[i] is positive and as small as possible when P[i] is the largest value still strictly below P[j]. That is a predecessor query on the prefix sums in the window, which a sorted multiset answers in O(log n).
Trying every length for every end is O(n * (r - l + 1)) and passes easily at n <= 100. The sorted window removes the dependence on r - l.
Approach
- Build
PwithP[0] = 0. - For
jfromlton:- Add
P[j - l]to the window (the newest allowed start). - If
j - r - 1 >= 0, removeP[j - r - 1](that start would make the subarray longer thanr). - Find the largest value in the window that is
< P[j]. If it exists, updatebestwithP[j]minus it.
- Add
- Return
best, or-1if nothing was found.
Java keeps the window in a TreeMap<Integer, Integer> used as a multiset (equal prefix sums are common) and calls lowerKey. Python uses bisect on a sorted list. Its searches are O(log r), but insort and pop shift elements, so the honest bound is O(n * r). That's irrelevant at this size, and it avoids depending on sortedcontainers.
Complexity
- Time: O(n log n) in Java; O(n * r) in Python because of list shifts
- Space: O(n)
Edge Cases
- No positive sum anywhere (example 2): return
-1 - A sum of exactly 0 is not positive, so the predecessor search must be strict (
lowerKey,bisect_left - 1), notfloorKey - Equal prefix sums inside the window: the window has to be a multiset, or removing one copy would drop another start that is still allowed
l = r: the window holds a single prefix sum, so this becomes a fixed-size sliding windowl = 1: single elements count, so any positive element is a candidate- Sums stay within
100 * 1000, sointis fine
Code
from bisect import bisect_left, insort
from typing import List
class Solution:
def minimumSumSubarray(self, nums: List[int], l: int, r: int) -> int:
"""
3364. Minimum Positive Sum Subarray
Time: O(n * r), from list inserts; the searches are O(log r)
Space: O(n)
"""
prefix = [0]
for x in nums:
prefix.append(prefix[-1] + x)
# window = sorted prefix[i] for every allowed start i in [j - r, j - l]
window = []
best = float("inf")
for j in range(l, len(prefix)):
insort(window, prefix[j - l])
if j - r - 1 >= 0:
window.pop(bisect_left(window, prefix[j - r - 1]))
# The largest prefix[i] < prefix[j] gives the smallest positive sum.
idx = bisect_left(window, prefix[j]) - 1
if idx >= 0:
best = min(best, prefix[j] - window[idx])
return best if best != float("inf") else -1import java.util.*;
/**
* 3364. Minimum Positive Sum Subarray
* Time: O(n log n)
* Space: O(n)
*/
class Solution {
public int minimumSumSubarray(List<Integer> nums, int l, int r) {
int n = nums.size();
int[] prefix = new int[n + 1];
for (int i = 0; i < n; i++) {
prefix[i + 1] = prefix[i] + nums.get(i);
}
// window = multiset of prefix[i] for every allowed start i in [j - r, j - l]
TreeMap<Integer, Integer> window = new TreeMap<>();
int best = Integer.MAX_VALUE;
for (int j = l; j <= n; j++) {
window.merge(prefix[j - l], 1, Integer::sum);
if (j - r - 1 >= 0) {
int old = prefix[j - r - 1];
if (window.merge(old, -1, Integer::sum) == 0) {
window.remove(old);
}
}
// The largest prefix[i] < prefix[j] gives the smallest positive sum.
Integer below = window.lowerKey(prefix[j]);
if (below != null) {
best = Math.min(best, prefix[j] - below);
}
}
return best == Integer.MAX_VALUE ? -1 : best;
}
}