Running sum from each start
class Solution: def minimumSumSubarray(self, nums, l, r): best = -1 for start in range(len(nums)): window_sum = 0 last = min(start + r, len(nums)) # never longer than r for end in range(start, last): window_sum += nums[end] # reuse the previous sum length = end - start + 1 if length >= l and window_sum > 0: if best == -1 or window_sum < best: best = window_sum return best
The code from the episode, ready for LeetCode's Python 3 editor: paste it in and submit.
Five goods on a market counter, one of them tied to a balloon, and a brass scale that must read above zero. We watch the needle dip below zero and climb back to find the lightest basket of two or three neighbours, and see why growing one running sum from every start finds it without weighing anything twice.
class Solution: def minimumSumSubarray(self, nums, l, r): best = -1 for length in range(l, r + 1): for start in range(len(nums) - length + 1): # Re-adds the whole slice: wasted work total = sum(nums[start:start + length]) if total > 0 and (best == -1 or total < best): best = total return best