LeetCode 3364 - Minimum Positive Sum Subarray

LeetCode Problem 3364

Difficulty: 🟢 Easy
Topics: Array, Sliding Window, Prefix Sum

Solution

Problem Understanding

The problem asks us to find the smallest positive sum among all subarrays whose lengths fall within a given range [l, r].

A subarray is a contiguous section of the array. We are allowed to choose any non-empty contiguous segment as long as:

1. Its length is between l and r, inclusive.
2. Its sum is strictly greater than 0.

Among all such valid subarrays, we must return the minimum positive sum. If no valid subarray exists, we return -1.

The input consists of:

• nums, an integer array
• l, the minimum allowed subarray length
• r, the maximum allowed subarray length

The output is a single integer representing the smallest positive subarray sum that satisfies the length restriction.

The constraints are relatively small:

• nums.length <= 100
• Each value is between -1000 and 1000

These limits are important because they tell us that even an O(n^2) or O(n^3) solution could potentially pass. However, we still want to design a clean and efficient solution.

Several edge cases are important:

• Every valid subarray may have a non-positive sum, in which case we return -1.
• The array may contain all negative numbers.
• The minimum positive sum could come from a larger subarray, not necessarily the shortest one.
• Multiple subarrays may produce the same minimum positive sum.
• The range [l, r] may span the entire array.
• Single-element subarrays are possible when l = 1.

Because the problem asks for the minimum positive sum, we must carefully ignore sums that are 0 or negative.

Approaches

Brute Force Approach

The most direct solution is to generate every possible subarray whose length lies between l and r.

For each starting index:

1. Try every allowed subarray length.
2. Compute the subarray sum.
3. If the sum is positive, update the answer with the minimum value seen so far.

A naive implementation would recompute every subarray sum from scratch. Since each sum computation may take O(n) time, the total complexity becomes O(n^3).

This works because we explicitly examine every valid subarray, guaranteeing that we never miss the optimal answer. However, repeatedly summing overlapping ranges is inefficient.

Improved Approach Using Prefix Sums

The key observation is that subarray sums can be computed efficiently using prefix sums.

If:

$$\text{prefix}[i]$$

stores the sum of the first i elements, then the sum of subarray:

$$nums[left:right]$$

can be computed in constant time as:

$$\text{prefix}[right] - \text{prefix}[left]$$

This avoids recomputing sums repeatedly.

We still enumerate all valid subarrays, but each sum calculation becomes O(1) instead of O(n).

Since the array size is only 100, this O(n^2) solution is both simple and efficient.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n³)	O(1)	Recomputes each subarray sum repeatedly
Optimal	O(n²)	O(n)	Uses prefix sums for constant-time range sum queries

Algorithm Walkthrough

Optimal Prefix Sum Algorithm

1. Create a prefix sum array of size n + 1.

The prefix sum at index i stores the total sum of the first i elements. This allows fast subarray sum computation. 2. Initialize the answer variable.

We can initialize it to infinity so that any positive sum found becomes the current best answer. 3. Iterate through every possible starting index.

For each start, we will try all valid subarray lengths between l and r. 4. Compute the ending index.

For a chosen length length, the ending position becomes:

$$end = start + length$$

If end exceeds the array size, we stop checking longer lengths. 5. Compute the subarray sum using prefix sums.

The sum of the subarray from start to end - 1 is:

$\text{sum} = \text{prefix}[end] - \text{prefix}[start]$

This computation takes constant time. 6. Check whether the sum is positive.

If the sum is greater than 0, update the answer with the minimum value seen so far. 7. After examining all valid subarrays, return the result.

If the answer was never updated, return -1.

Why it works

The algorithm systematically checks every subarray whose length lies in [l, r]. Prefix sums guarantee that every subarray sum is computed correctly in constant time. Since we only update the answer when a smaller positive sum is found, the final answer is guaranteed to be the minimum positive subarray sum among all valid candidates.

Python Solution

from typing import List

class Solution:
    def minimumSumSubarray(self, nums: List[int], l: int, r: int) -> int:
        n = len(nums)

        # Build prefix sum array
        prefix = [0] * (n + 1)

        for i in range(n):
            prefix[i + 1] = prefix[i] + nums[i]

        minimum_positive_sum = float("inf")

        # Try every starting index
        for start in range(n):

            # Try every allowed subarray length
            for length in range(l, r + 1):
                end = start + length

                if end > n:
                    break

                current_sum = prefix[end] - prefix[start]

                if current_sum > 0:
                    minimum_positive_sum = min(
                        minimum_positive_sum,
                        current_sum
                    )

        return minimum_positive_sum if minimum_positive_sum != float("inf") else -1

The implementation begins by constructing a prefix sum array. Each entry stores the cumulative sum up to that point in the array.

Next, we iterate through every possible starting index. For each starting position, we try every valid subarray length from l to r.

The prefix sum array allows us to compute each subarray sum in constant time instead of summing elements manually. Whenever we encounter a positive sum, we compare it with the current best answer and keep the smaller value.

At the end, if no positive subarray sum was found, the answer remains infinity, so we return -1.

Go Solution

package main

import "math"

func minimumSumSubarray(nums []int, l int, r int) int {
	n := len(nums)

	// Build prefix sum array
	prefix := make([]int, n+1)

	for i := 0; i < n; i++ {
		prefix[i+1] = prefix[i] + nums[i]
	}

	minimumPositiveSum := math.MaxInt

	// Try every starting index
	for start := 0; start < n; start++ {

		// Try every allowed length
		for length := l; length <= r; length++ {
			end := start + length

			if end > n {
				break
			}

			currentSum := prefix[end] - prefix[start]

			if currentSum > 0 && currentSum < minimumPositiveSum {
				minimumPositiveSum = currentSum
			}
		}
	}

	if minimumPositiveSum == math.MaxInt {
		return -1
	}

	return minimumPositiveSum
}

The Go implementation follows the same logic as the Python version.

One small difference is that Go does not have a built-in infinity value for integers, so we use math.MaxInt as the initial sentinel value.

Go slices are used for the prefix sum array, and all computations remain integer-safe because the constraints are small enough that overflow is not a concern.

Worked Examples

Example 1

Input:

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

Prefix sum array:

Index	Prefix Sum
0	0
1	3
2	1
3	2
4	6

Now examine all valid subarrays.

Start	Length	End	Subarray	Sum	Valid?
0	2	2	[3, -2]	1	Yes
0	3	3	[3, -2, 1]	2	Yes
1	2	3	[-2, 1]	-1	No
1	3	4	[-2, 1, 4]	3	Yes
2	2	4	[1, 4]	5	Yes

The smallest positive sum is 1.

Output:

1

Example 2

Input:

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

Prefix sums:

Index	Prefix Sum
0	0
1	-2
2	0
3	-3
4	-2

Valid checks:

Subarray	Sum
[-2, 2]	0
[-2, 2, -3]	-3
[2, -3]	-1
[2, -3, 1]	0
[-3, 1]	-2

No positive sums exist.

Output:

-1

Example 3

Input:

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

Possible valid sums:

Subarray	Sum
[1, 2]	3
[2, 3]	5
[3, 4]	7
[1, 2, 3]	6
[2, 3, 4]	9
[1, 2, 3, 4]	10

The minimum positive sum is 3.

Output:

3

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n²)	We examine all valid subarrays
Space	O(n)	Prefix sum array requires linear extra space

The outer loop iterates over all starting indices, and the inner loop iterates over all allowed lengths. Since the maximum array size is only 100, this approach is very efficient in practice.

The prefix sum array stores cumulative sums for fast range queries, which requires O(n) additional memory.

Test Cases

from typing import List

class Solution:
    def minimumSumSubarray(self, nums: List[int], l: int, r: int) -> int:
        n = len(nums)

        prefix = [0] * (n + 1)

        for i in range(n):
            prefix[i + 1] = prefix[i] + nums[i]

        answer = float("inf")

        for start in range(n):
            for length in range(l, r + 1):
                end = start + length

                if end > n:
                    break

                current_sum = prefix[end] - prefix[start]

                if current_sum > 0:
                    answer = min(answer, current_sum)

        return answer if answer != float("inf") else -1

sol = Solution()

assert sol.minimumSumSubarray([3, -2, 1, 4], 2, 3) == 1
# Example 1

assert sol.minimumSumSubarray([-2, 2, -3, 1], 2, 3) == -1
# Example 2

assert sol.minimumSumSubarray([1, 2, 3, 4], 2, 4) == 3
# Example 3

assert sol.minimumSumSubarray([5], 1, 1) == 5
# Single positive element

assert sol.minimumSumSubarray([-5], 1, 1) == -1
# Single negative element

assert sol.minimumSumSubarray([0], 1, 1) == -1
# Zero is not positive

assert sol.minimumSumSubarray([1, -1, 1, -1], 1, 2) == 1
# Minimum positive single-element subarray

assert sol.minimumSumSubarray([-1, -2, -3], 1, 3) == -1
# All negative numbers

assert sol.minimumSumSubarray([2, 2, 2], 2, 3) == 4
# Multiple valid subarrays

assert sol.minimumSumSubarray([10, -9, 1], 2, 2) == 1
# Smallest positive sum appears late

assert sol.minimumSumSubarray([100, -99, 50], 2, 3) == 1
# Prefix sum handling

assert sol.minimumSumSubarray([1, 1, 1, 1], 4, 4) == 4
# Entire array only

Test	Why
[3, -2, 1, 4], l=2, r=3	Validates standard mixed-number scenario
[-2, 2, -3, 1], l=2, r=3	Ensures -1 is returned when no positive sum exists
[1, 2, 3, 4], l=2, r=4	Checks normal positive-only array
[5], l=1, r=1	Smallest valid input
[-5], l=1, r=1	Single negative element
[0], l=1, r=1	Zero should not count as positive
[1, -1, 1, -1], l=1, r=2	Mixed positive and negative values
[-1, -2, -3], l=1, r=3	All negative array
[2, 2, 2], l=2, r=3	Multiple overlapping valid subarrays
[10, -9, 1], l=2, r=2	Minimum positive sum occurs later
[100, -99, 50], l=2, r=3	Verifies prefix sum correctness
[1, 1, 1, 1], l=4, r=4	Only full-array subarray allowed

Edge Cases

One important edge case occurs when no positive subarray sum exists. This can happen when the array contains only negative numbers or when every valid subarray sums to zero or less. A buggy implementation might accidentally return 0 or an uninitialized value. This implementation avoids that problem by initializing the answer to infinity and only updating it for strictly positive sums.

Another important case is when l = r = 1. In this situation, only single-element subarrays are allowed. The implementation still works naturally because the nested loops examine subarrays of exactly one element, and the prefix sum computation remains valid.

A third edge case involves subarrays near the end of the array. If the chosen length causes the subarray to extend beyond the array boundary, accessing invalid indices could cause errors. The implementation handles this safely with:

if end > n:
    break

This ensures that only valid subarrays are processed.

A final subtle case occurs when the minimum positive sum is very small and surrounded by larger sums. For example:

[100, -99, 50]

The correct answer is 1, from the subarray [100, -99]. Since the algorithm checks every valid subarray and always keeps the smallest positive sum seen so far, it correctly identifies this optimal value.