3364. Minimum Positive Sum Subarray

Problem Description

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.

Intuition

To solve this problem, the goal is to find a subarray within the array nums that satisfies two conditions: its length is between l and r, and its sum is greater than zero. Among all possible subarrays that meet these criteria, we want to find the one with the smallest sum.

The approach involves checking each possible starting point i of a subarray, and for each starting point, incrementally extending the subarray to include more elements, one at a time, until the end of the array is reached. By maintaining a running sum for the subarray, we can efficiently compute the sum of any subarray defined by a starting point i and an ending point j.

For each subarray from i to j, we need to verify if its length is within the bounds l and r and if its sum is positive. If these conditions are satisfied, we compare its sum with the current minimum sum found so far and update the minimum if the current sum is smaller.

Finally, if no subarray meeting the conditions is found, we return -1. Otherwise, we return the minimum sum found.

Learn more about Prefix Sum and Sliding Window patterns.

Solution Approach

The solution employs a brute-force enumeration strategy to explore all possible subarrays of nums that could be the answer. Here's a detailed breakdown of the approach:

Initialization:
- Begin by setting a variable ans to inf, representing the smallest sum found for subarrays that meet the criteria. If ans remains inf, it implies no suitable subarray was found.
Enumeration of Subarrays:
- Iterate over each possible starting index i of the subarray. For each i, initialize a sum s to zero.
- From this starting index i, iterate through the subsequent elements to create the subarray ending at index j.
- Maintain a running sum s that adds each element nums[j] from index i to j.
Verification and Update:
- For each subarray from i to j, check whether its length falls within the bounds [l, r] using the condition l <= j - i + 1 <= r.
- Check if the subarray sum s is greater than zero. If both conditions are true, update ans to be the minimum of the current ans and the sum s.
Result Determination:
- After all subarrays have been considered, return -1 if no valid subarray has been found (i.e., ans is still inf). Otherwise, return ans.

This approach is simple and direct, involving the use of nested loops to evaluate all possible subarrays, while leveraging a simple mathematical check to ensure the subarray meets the given conditions.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Consider an example where nums = [4, -1, 2, 1, -5, 6], l = 1, and r = 3.

Step-by-step Walkthrough:

Initialization:
- Set ans to inf to record the minimum sum found for subarrays meeting the criteria.
Enumeration of Subarrays:
- Start with i = 0, initialize s = 0.
  - For j = 0: Add nums[0] = 4 to s. So s = 4.
    - Subarray: [4] with length 1. Since 1 <= 1 <= 3 and sum is positive, update ans = 4.
  - For j = 1: Add nums[1] = -1 to s. So s = 3.
    - Subarray: [4, -1] with length 2. Since 1 <= 2 <= 3 and sum is positive, update ans = 3.
  - For j = 2: Add nums[2] = 2 to s. So s = 5.
    - Subarray: [4, -1, 2] with length 3. Since 1 <= 3 <= 3 and sum is positive, ans remains 3.
- Starting with i = 1, initialize s = 0.
  - For j = 1: Add nums[1] = -1 to s. So s = -1.
    - Subarray: [-1] with length 1. Sum is not positive, ans remains 3.
  - For j = 2: Add nums[2] = 2 to s. So s = 1.
    - Subarray: [-1, 2] with length 2. Since 1 <= 2 <= 3 and sum is positive, update ans = 1.
  - For j = 3: Add nums[3] = 1 to s. So s = 2.
    - Subarray: [-1, 2, 1] with length 3. Since 1 <= 3 <= 3 and sum is positive, ans remains 1.
- Starting with i = 2, initialize s = 0.
  - For j = 2: Add nums[2] = 2 to s. So s = 2.
    - Subarray: [2] with length 1. Since 1 <= 1 <= 3 and sum is positive, ans remains 1.
  - For j = 3: Add nums[3] = 1 to s. So s = 3.
    - Subarray: [2, 1] with length 2. Sum is positive but ans remains 1.
  - For j = 4: Add nums[4] = -5 to s. So s = -2.
    - Subarray: [2, 1, -5] with length 3. Sum is not positive, ans remains 1.
- Continue evaluating subarrays starting at i = 3, i = 4, and i = 5 similar to above logic, but none will yield a smaller positive sum than 1.
Result Determination:
- After evaluating all possible subarrays, the smallest positive sum found is 1. Thus, return 1 as the minimum sum of a subarray meeting the conditions.

This process rigorously checks each potential candidate, ensuring the smallest possible subarray sum is identified.

Solution Implementation

1from typing import List
2from math import inf
3
4class Solution:
5    def minimumSumSubarray(self, nums: List[int], l: int, r: int) -> int:
6        n = len(nums)  # Get the length of the input list
7        ans = inf  # Initialize the answer to infinity
8      
9        # Iterate over each starting point of the subarray
10        for i in range(n):
11            s = 0  # Initialize the current subarray sum to 0
12          
13            # Iterate over each ending point of the subarray starting from i
14            for j in range(i, n):
15                s += nums[j]  # Add the current element to the subarray sum
16              
17                # Check if the current subarray length is within the given range [l, r]
18                # and whether the sum is greater than 0
19                if l <= (j - i + 1) <= r and s > 0:
20                    ans = min(ans, s)  # Update the minimum positive subarray sum
21      
22        # Return -1 if no valid subarray sum was found, otherwise return the minimum sum
23        return -1 if ans == inf else ans
24

1import java.util.List;
2
3class Solution {
4    public int minimumSumSubarray(List<Integer> nums, int l, int r) {
5        int n = nums.size();  // Get the size of the list
6        final int INF = Integer.MAX_VALUE;  // Define a constant for infinity
7        int minSum = INF;  // Initialize the minimum sum as infinity
8
9        // Iterate over each starting point of the subarray
10        for (int i = 0; i < n; ++i) {
11            int currentSum = 0;  // Initialize the current sum of the subarray
12
13            // Iterate over each ending point of the subarray
14            for (int j = i; j < n; ++j) {
15                currentSum += nums.get(j);  // Add the current element to the sum
16                int k = j - i + 1;  // Calculate the length of the current subarray
17
18                // Check if the subarray length is within the specified range and has a positive sum
19                if (k >= l && k <= r && currentSum > 0) {
20                    minSum = Math.min(minSum, currentSum);  // Update the minimum sum if a smaller positive sum is found
21                }
22            }
23        }
24
25        // If no valid subarray is found, return -1; otherwise, return the minimum sum found
26        return minSum == INF ? -1 : minSum;
27    }
28}
29

1#include <vector>
2#include <algorithm>
3#include <climits>
4
5class Solution {
6public:
7    int minimumSumSubarray(std::vector<int>& nums, int l, int r) {
8        int n = nums.size();
9        const int INF = INT_MAX; // Define infinity as the maximum integer value
10        int answer = INF; // Initialize answer with infinity
11
12        // Iterate over each starting point of the subarray
13        for (int start = 0; start < n; ++start) {
14            int currentSum = 0; // Initialize the current sum of the subarray
15
16            // Iterate to find subarrays starting from 'start' index
17            for (int end = start; end < n; ++end) {
18                currentSum += nums[end]; // Add the current element to the subarray sum
19                int length = end - start + 1; // Calculate the length of the current subarray
20
21                // Check if the subarray length is within bounds and the sum is positive
22                if (length >= l && length <= r && currentSum > 0) {
23                    answer = std::min(answer, currentSum); // Update the answer with the minimum positive subarray sum
24                }
25            }
26        }
27
28        // If the answer is still infinity, return -1, otherwise return the minimum sum found
29        return answer == INF ? -1 : answer;
30    }
31};
32

1// This function finds the minimum sum of any continuous subarray in `nums`
2// with a length between `l` and `r`, inclusive. If all sums are non-positive,
3// it returns -1.
4function minimumSumSubarray(nums: number[], l: number, r: number): number {
5    const n = nums.length; // Determine the length of the input array
6    let ans = Infinity; // Initialize the minimum sum to infinity
7
8    // Iterate over each starting point of the subarray
9    for (let i = 0; i < n; ++i) {
10        let currentSum = 0; // Initialize the current sum to 0
11
12        // Iterate over each ending point of the subarray starting from i
13        for (let j = i; j < n; ++j) {
14            currentSum += nums[j]; // Add the current element to the current sum
15            const currentLength = j - i + 1; // Calculate the current subarray length
16
17            // Check if the current subarray meets the length condition
18            // and if the sum is positive
19            if (currentLength >= l && currentLength <= r && currentSum > 0) {
20                ans = Math.min(ans, currentSum); // Update the minimum sum if needed
21            }
22        }
23    }
24
25    // If no valid subarray was found (ans remained infinity), return -1
26    return ans === Infinity ? -1 : ans;
27}
28

Time and Space Complexity

The time complexity of the given code is O(n^2), where n is the length of the array nums. This is because there are two nested loops: the outer loop iterates over each starting point of the subarray in O(n) time, and the inner loop iterates over each ending point for that starting point, also in O(n) time. Therefore, the overall complexity is O(n * n).

The space complexity is O(1) because the algorithm uses a constant amount of additional space regardless of the input size. The variables n, ans, i, s, and j are used, which have a space complexity that does not depend on n.

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

Is the following code DFS or BFS?

void search(Node root) {
  if (!root) return;
  visit(root);
  root.visited = true;
  for (Node node in root.adjacent) {
    if (!node.visited) {
      search(node);
    }
  }
}

Depth First Search

Breadth First Search

I don’t know