# Minimum Positive Sum Subarray 
**Difficulty:** EASY
[External](https://leetcode.com/problems/minimum-positive-sum-subarray)
Canonical: https://scaleengineer.com/dsa/problems/minimum-positive-sum-subarray
**Patterns:** [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window), [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Data structures:** Array
---
## Problem
You are given an integer array `nums` and **two** integers `l` and `r`. Your task is to find the **minimum** sum of a **subarray** whose size is between `l` and `r` (inclusive) and whose sum is greater than 0.

Return the **minimum** sum of such a subarray. If no such subarray exists, return -1.

A **subarray** is a contiguous **non-empty** sequence of elements within an array.

**Example 1:**

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

**Output:** 1

**Explanation:**

The subarrays of length between `l = 2` and `r = 3` where the sum is greater than 0 are:

* `[3, -2]` with a sum of 1
* `[1, 4]` with a sum of 5
* `[3, -2, 1]` with a sum of 2
* `[-2, 1, 4]` with a sum of 3

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

**Explanation:**

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

**Explanation:**

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`

# Approaches
## Brute Force Iteration
This approach involves checking every possible subarray that meets the length criteria. We generate all subarrays, check their length, calculate their sum, and if the sum is positive, we compare it with the minimum positive sum found so far.
**Time:** O(N^3), where N is the length of `nums`. The three nested loops for `i` (start index), `j` (end index), and `k` (summation) lead to a cubic time complexity. · **Space:** O(1), as we only use a few variables to store indices and the minimum sum. No additional data structures that scale with input size are needed.
**Pros:** Simple to understand and implement.; Requires no extra space.
**Cons:** Highly inefficient due to its cubic time complexity.; Will likely time out on larger input sizes, although it's acceptable for the given constraints (N <= 100).
### Explanation
The brute-force solution is the most straightforward way to solve the problem. We use three nested loops. The outer two loops, with indices `i` and `j`, are used to define the start and end of every possible subarray. The third, innermost loop, with index `k`, iterates from `i` to `j` to compute the sum of the elements in the current subarray.

Before calculating the sum, we first verify if the length of the subarray, given by `j - i + 1`, falls within the specified range `[l, r]`. If it does, we proceed to calculate its sum. We maintain a variable, `minSum`, initialized to a very large value. If a subarray's sum is found to be positive, we update `minSum` to be the minimum of its current value and the new positive sum. After checking all subarrays, if `minSum` has not been updated, we conclude that no such subarray exists and return -1. Otherwise, we return the final `minSum`.

```java
class Solution {
    public int minPositiveSum(int[] nums, int l, int r) {
        int n = nums.length;
        long minSum = Long.MAX_VALUE;

        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                int len = j - i + 1;
                if (len >= l && len <= r) {
                    long currentSum = 0;
                    for (int k = i; k <= j; k++) {
                        currentSum += nums[k];
                    }
                    if (currentSum > 0) {
                        minSum = Math.min(minSum, currentSum);
                    }
                }
            }
        }

        return minSum == Long.MAX_VALUE ? -1 : (int) minSum;
    }
}
```
### Algorithm
- Initialize `minSum` to a very large value (e.g., `Long.MAX_VALUE`).
- Get the length of the array, `n`.
- Use a nested loop to iterate through all possible start indices `i` from `0` to `n - 1`.
- Inside this loop, use another nested loop to iterate through all possible end indices `j` from `i` to `n - 1`.
- For each pair `(i, j)`, calculate the length of the subarray `len = j - i + 1`.
- Check if the length `len` is within the required range `[l, r]`.
- If the length is valid, use a third loop to calculate the sum of the subarray `nums[i...j]`.
- If the calculated `currentSum` is greater than 0, update `minSum = Math.min(minSum, currentSum)`.
- After all loops complete, if `minSum` is still `Long.MAX_VALUE`, it means no valid subarray was found, so return -1.
- Otherwise, return `minSum`.

## Optimized Brute Force with Prefix Sums
This approach improves upon the brute-force method by pre-calculating prefix sums. A prefix sum array allows us to find the sum of any subarray in constant time, which reduces the overall complexity from cubic to quadratic.
**Time:** O(N^2), where N is the length of `nums`. The prefix sum calculation takes O(N), and the two nested loops to check all valid subarrays take O(N^2). · **Space:** O(N) to store the prefix sum array.
**Pros:** Significantly faster than the O(N^3) approach.; Still relatively easy to implement.
**Cons:** Requires O(N) extra space for the prefix sum array.; Can be too slow for larger N (e.g., N > 5000), but is efficient enough for the given constraints.
### Explanation
To optimize the brute-force approach, we can avoid the repeated summation in the innermost loop. This is achieved by pre-computing a prefix sum array. Let's call it `prefix`, where `prefix[i]` stores the sum of all elements from `nums[0]` to `nums[i-1]`. We set `prefix[0]` to 0.

Once the `prefix` array is built in O(N) time, the sum of any subarray `nums[i...j]` can be calculated in O(1) time using the formula `prefix[j+1] - prefix[i]`. We then proceed with the two nested loops to iterate through all possible start (`i`) and end (`j`) indices. For each subarray that satisfies the length constraint `l <= j - i + 1 <= r`, we compute its sum in constant time and update our `minSum` if the sum is positive and smaller than the current `minSum`. This optimization effectively removes one level of looping, improving the time complexity.

```java
class Solution {
    public int minPositiveSum(int[] nums, int l, int r) {
        int n = nums.length;
        long[] prefix = new long[n + 1];
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }

        long minSum = Long.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            for (int j = i + l - 1; j < n; j++) {
                int len = j - i + 1;
                if (len > r) {
                    break; // Optimization: lengths will only increase
                }
                long currentSum = prefix[j + 1] - prefix[i];
                if (currentSum > 0) {
                    minSum = Math.min(minSum, currentSum);
                }
            }
        }

        return minSum == Long.MAX_VALUE ? -1 : (int) minSum;
    }
}
```
### Algorithm
- Get the length of the array, `n`.
- Create a prefix sum array `prefix` of size `n + 1`. Initialize `prefix[0] = 0`.
- Populate the `prefix` array: for `k` from `0` to `n-1`, set `prefix[k+1] = prefix[k] + nums[k]`.
- Initialize `minSum = Long.MAX_VALUE`.
- Iterate `i` from `0` to `n - 1` (start index).
-   Iterate `j` from `i + l - 1` to `n - 1` (end index).
-     Check if the length `len = j - i + 1` is within `[l, r]`.
-     If it is, calculate `currentSum = prefix[j+1] - prefix[i]`.
-     If `currentSum > 0`, update `minSum = Math.min(minSum, currentSum)`.
- After the loops, if `minSum` is still `Long.MAX_VALUE`, return -1.
- Otherwise, return `(int)minSum`.

## Sliding Window with TreeSet
This is the most efficient approach, combining prefix sums with a sliding window and a balanced binary search tree (implemented as `TreeSet` in Java). This allows us to find the optimal subarray sum in a more targeted and efficient manner.
**Time:** O(N log K), where N is the length of `nums` and K is the size of the window (`r - l + 1`). Each of the N iterations involves `add`, `remove`, and `lower` operations on the `TreeSet`, which take O(log K) time. In the worst case, K can be O(N), making the complexity O(N log N). · **Space:** O(N), for the prefix sum array. The `TreeSet` stores at most `r - l + 1` elements, which is O(N) in the worst case.
**Pros:** Most efficient solution with O(N log N) time complexity.; Scales well for larger input sizes.
**Cons:** More complex to understand and implement correctly.; The constant factors associated with `TreeSet` operations might make it slower than the O(N^2) approach for very small N, but its asymptotic complexity is superior.
### Explanation
The core idea is to rephrase the problem using prefix sums. We want to find `min(prefix[j] - prefix[i]) > 0` subject to `l <= j-i <= r`. For each possible endpoint `j-1` of a subarray, we need to find an optimal start point `i` within the valid window `[j-r, j-l]`.

Specifically, for a fixed `prefix[j]`, we want to find a `prefix[i]` from the valid window such that `prefix[i]` is as close as possible to `prefix[j]` but still smaller. This will minimize the positive difference `prefix[j] - prefix[i]`.

A `TreeSet` (a balanced binary search tree) is the ideal data structure for this task. It can maintain the set of `prefix[i]` values for the sliding window of start indices in sorted order. As we iterate `j` from `l` to `n`, we update the window by adding the new potential `prefix[j-l]` and removing the now-out-of-range `prefix[j-r-1]`. For each `j`, we query the `TreeSet` for the largest element strictly less than `prefix[j]` using the `lower()` method. This query takes logarithmic time, leading to an overall efficient solution.

```java
import java.util.TreeSet;

class Solution {
    public int minPositiveSum(int[] nums, int l, int r) {
        int n = nums.length;
        long[] prefix = new long[n + 1];
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }

        long minSum = Long.MAX_VALUE;
        TreeSet<Long> bst = new TreeSet<>();

        for (int j = l; j <= n; j++) {
            // Add the prefix sum for the start of a window of length l
            bst.add(prefix[j - l]);
            
            // Remove the prefix sum that is now outside the window of length r
            if (j > r) {
                bst.remove(prefix[j - r - 1]);
            }

            // Find the largest prefix sum in the window smaller than prefix[j]
            Long p = bst.lower(prefix[j]);
            if (p != null) {
                minSum = Math.min(minSum, prefix[j] - p);
            }
        }

        return minSum == Long.MAX_VALUE ? -1 : (int) minSum;
    }
}
```
### Algorithm
- Calculate the prefix sum array `prefix` of size `n+1`, with `prefix[0] = 0`.
- Initialize `minSum = Long.MAX_VALUE`.
- Initialize an empty `TreeSet<Long>` named `bst` to store prefix sums of potential starting points.
- Iterate `j` from `l` to `n`. The index `j` corresponds to the end of a prefix, `prefix[j]`, which represents the sum of a subarray ending at index `j-1`.
-   **Maintain the window of start indices:**
    - Add `prefix[j-l]` to the `bst`. This corresponds to the prefix sum for a subarray of length `l` ending at `j-1`.
    - If `j > r`, it means a subarray starting at `j-r-1` and ending at `j-1` would have length `r+1`, which is too long. So, remove `prefix[j-r-1]` from the `bst`.
-   **Query for minimum sum:**
    - We want to find `min(prefix[j] - p) > 0`, where `p` is a prefix sum from the `bst`. This is equivalent to finding the largest `p` in `bst` such that `p < prefix[j]`.
    - Use `bst.lower(prefix[j])` to find this value `p`.
    - If such a `p` exists, calculate the sum `prefix[j] - p` and update `minSum = Math.min(minSum, prefix[j] - p)`.
- After the loop, if `minSum` was not updated, return -1. Otherwise, return `(int)minSum`.

# Solutions
### Java

```java
class Solution {
public
  int minimumSumSubarray(List<Integer> nums, int l, int r) {
    int n = nums.size();
    final int inf = Integer.MAX_VALUE;
    int ans = inf;
    for (int i = 0; i < n; ++i) {
      int s = 0;
      for (int j = i; j < n; ++j) {
        s += nums.get(j);
        int k = j - i + 1;
        if (k >= l && k <= r && s > 0) {
          ans = Math.min(ans, s);
        }
      }
    }
    return ans == inf ? -1 : ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minimumSumSubarray(vector<int> &nums, int l, int r) {
    int n = nums.size();
    const int inf = INT_MAX;
    int ans = inf;
    for (int i = 0; i < n; ++i) {
      int s = 0;
      for (int j = i; j < n; ++j) {
        s += nums[j];
        int k = j - i + 1;
        if (k >= l && k <= r && s > 0) {
          ans = min(ans, s);
        }
      }
    }
    return ans == inf ? -1 : ans;
  }
};

```

### Python

```python
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

```