Minimum Positive Sum Subarray
EasyPrompt
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 <= 1001 <= l <= r <= nums.length-1000 <= nums[i] <= 1000
Approaches
3 approaches with complexity analysis and trade-offs.
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.
Algorithm
- Initialize
minSumto 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
ifrom0ton - 1. - Inside this loop, use another nested loop to iterate through all possible end indices
jfromiton - 1. - For each pair
(i, j), calculate the length of the subarraylen = j - i + 1. - Check if the length
lenis 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
currentSumis greater than 0, updateminSum = Math.min(minSum, currentSum). - After all loops complete, if
minSumis stillLong.MAX_VALUE, it means no valid subarray was found, so return -1. - Otherwise, return
minSum.
Walkthrough
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.
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; }}Complexity
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.
Trade-offs
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).
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.
Algorithm
- Get the length of the array,
n. - Create a prefix sum array
prefixof sizen + 1. Initializeprefix[0] = 0. - Populate the
prefixarray: forkfrom0ton-1, setprefix[k+1] = prefix[k] + nums[k]. - Initialize
minSum = Long.MAX_VALUE. - Iterate
ifrom0ton - 1(start index). - Iterate
jfromi + l - 1ton - 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
minSumis stillLong.MAX_VALUE, return -1. - Otherwise, return
(int)minSum.
Walkthrough
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.
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; }}Complexity
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.
Trade-offs
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.
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.
Algorithm
- Calculate the prefix sum array
prefixof sizen+1, withprefix[0] = 0. - Initialize
minSum = Long.MAX_VALUE. - Initialize an empty
TreeSet<Long>namedbstto store prefix sums of potential starting points. - Iterate
jfromlton. The indexjcorresponds to the end of a prefix,prefix[j], which represents the sum of a subarray ending at indexj-1. - Maintain the window of start indices:
- Add
prefix[j-l]to thebst. This corresponds to the prefix sum for a subarray of lengthlending atj-1. - If
j > r, it means a subarray starting atj-r-1and ending atj-1would have lengthr+1, which is too long. So, removeprefix[j-r-1]from thebst.
- Add
- Query for minimum sum:
- We want to find
min(prefix[j] - p) > 0, wherepis a prefix sum from thebst. This is equivalent to finding the largestpinbstsuch thatp < prefix[j]. - Use
bst.lower(prefix[j])to find this valuep. - If such a
pexists, calculate the sumprefix[j] - pand updateminSum = Math.min(minSum, prefix[j] - p).
- We want to find
- After the loop, if
minSumwas not updated, return -1. Otherwise, return(int)minSum.
Walkthrough
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.
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; }}Complexity
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.
Trade-offs
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
TreeSetoperations might make it slower than the O(N^2) approach for very small N, but its asymptotic complexity is superior.
Solutions
Solution
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; }}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; }};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 ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.