Minimum Positive Sum Subarray

Easy

Amazon

2 views

Topics:

ArraysSliding Windows

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

Minimum Positive Sum Subarray

Easy

Amazon

2 views

Topics:

ArraysSliding Windows

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

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the expected return value if no subarray has a positive sum?
Can the input array contain negative numbers, zeros, or just positive integers?
What are the size constraints for the input array (number of elements)?
Should I return the shortest such subarray if there are multiple subarrays with the same minimum positive sum?
Is it acceptable to modify the input array, or should I treat it as immutable?

Brute Force Solution

Approach

The brute force method is about trying absolutely everything. For this problem, it means we will explore every possible group of numbers in the given list and check a specific property for each group.

Here's how the algorithm would work step-by-step:

First, consider the first number alone. Calculate the sum of this tiny group.
Next, consider the first two numbers as a group, calculate their sum.
Then consider the first three numbers, and so on, all the way to the end of the list. For each of these groups, compute their sum.
After that, start from the second number. Consider it alone, then together with the next number, then with the next two numbers, and so on. Compute the sum for each of these groups as well.
Continue this process, each time starting from the next number in the list, and forming groups of increasing size, until you've considered every possible group of numbers. Each time calculating the sum of these groups.
For each group of numbers that you calculated the sum for, check if their sum is positive.
Out of all the groups that have a positive sum, find the one with the smallest length (the one with the fewest numbers in the group).

Code Implementation

def minimum_positive_sum_subarray_brute_force(numbers):
    minimum_length = float('inf')
    
    # Iterate through all possible start indices of subarrays
    for start_index in range(len(numbers)): 

        # Iterate through all possible end indices for each start index
        for end_index in range(start_index, len(numbers)): 
            current_subarray = numbers[start_index:end_index + 1]
            current_sum = sum(current_subarray)
            
            # Check if the sum is positive
            if current_sum > 0:

                #Update min length if smaller subarray is found
                if len(current_subarray) < minimum_length:

                    minimum_length = len(current_subarray)

    # Handle edge case: no positive sum subarray found
    if minimum_length == float('inf'):
        return -1
    
    return minimum_length

Big(O) Analysis

Time Complexity

O(n³) – The brute force approach iterates through all possible subarrays. The outer loop iterates 'n' times, dictating the start of the subarray. The inner loop also iterates up to 'n' times, expanding the subarray to the right. Within the inner loop, the sum of the subarray is calculated, which itself takes O(n) time in the worst case. Therefore, the total time complexity is O(n * n * n), which simplifies to O(n³).

Space Complexity

O(1) – The brute force method described calculates the sum of each subarray on the fly without storing the subarrays themselves or the sums of all subarrays simultaneously. It only needs to store a few variables: indices to define the start and end of the subarray, the current subarray sum, and potentially the minimum length found so far. Therefore, the space used remains constant regardless of the input size N, resulting in O(1) auxiliary space complexity.

Optimal Solution

Approach

The goal is to find the shortest group of consecutive numbers that adds up to a positive amount. The key is to cleverly keep track of sums and their starting points to avoid recomputing things and focus on the most promising candidates.

Here's how the algorithm would work step-by-step:

Start from the beginning of the list of numbers and calculate the running total as you go.
Keep track of the smallest running total you've seen so far and where it started.
At each number, subtract the smallest running total you've seen previously from the current running total.
If this difference is positive, you've found a group of consecutive numbers that adds up to a positive amount.
Remember the length of this group of consecutive numbers and compare it to the shortest one you've found so far; update the shortest length if necessary.
Continue through the list of numbers, updating the smallest running total and checking for positive sums along the way.
The shortest length you've found at the end is the answer: the length of the minimum positive sum subarray.

Code Implementation

def find_minimum_positive_sum_subarray(numbers):
    minimum_length = float('inf')
    current_running_sum = 0
    minimum_running_sum = 0
    start_index_of_minimum_sum = 0

    for current_index, number in enumerate(numbers):
        current_running_sum += number

        # Check if subtracting the minimum running sum yields a positive sum.
        if current_running_sum - minimum_running_sum > 0:

            current_length = current_index - start_index_of_minimum_sum
            minimum_length = min(minimum_length, current_length)

        # Update minimum running sum and its starting index.
        if current_running_sum < minimum_running_sum:

            # Keep track of the smallest running sum seen so far.
            minimum_running_sum = current_running_sum

            start_index_of_minimum_sum = current_index + 1

    # Handle the case where no positive sum subarray exists.
    if minimum_length == float('inf'):
        return -1

    return minimum_length

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input array of size n exactly once to calculate the running sum and maintain the minimum prefix sum. Within the single loop, each operation such as calculating the running sum, subtracting the minimum prefix sum, and updating the minimum length is performed in constant time, O(1). Thus the time complexity is directly proportional to the input size n, resulting in a time complexity of O(n).

Space Complexity

O(1) – The algorithm maintains only a few scalar variables: the smallest running total seen so far, its starting index, the current running total, the length of the shortest positive sum subarray found so far, and potentially a few loop counters. The number of these variables does not depend on the input array's size N. Therefore, the algorithm uses constant extra space.

Edge Cases

Case	How to Handle
Empty input array	Return -1 since a subarray cannot be formed, indicating no solution.
Array with a single element	Return the element itself if positive, otherwise -1.
Array with all negative numbers	Return -1 since no subarray will have a positive sum.
Array with only zeros	Return -1 since no subarray will have a positive sum.
Array with very large positive numbers that could cause integer overflow when summed	Use long data type for calculating sums or implement a check to avoid integer overflow.
Array with negative numbers that could cause the minimum positive sum to be initially a very large value.	Initialize the minimum positive sum to positive infinity to ensure accurate comparison.
Array where all subarrays have sums greater than 0, but the entire array sum is the minimum positive sum	The algorithm should iterate through all possible subarrays, correctly identifying the entire array as the minimum.
Input array contains extreme boundary values (e.g. Integer.MAX_VALUE or Integer.MIN_VALUE)	Ensure calculations involving these values don't cause overflow or unexpected behavior.