3364. Minimum Positive Sum Subarray

  • Array
  • Sliding Window
  • Prefix Sum
TIME
O(n * r), from list inserts; the searches are O(log r)
SPACE
O(n)
problem on leetcode ↗source on github ↗

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

  1. Build P with P[0] = 0.
  2. For j from l to n:
    • Add P[j - l] to the window (the newest allowed start).
    • If j - r - 1 >= 0, remove P[j - r - 1] (that start would make the subarray longer than r).
    • Find the largest value in the window that is < P[j]. If it exists, update best with P[j] minus it.
  3. Return best, or -1 if 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), not floorKey
  • 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 window
  • l = 1: single elements count, so any positive element is a candidate
  • Sums stay within 100 * 1000, so int is 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 -1