Jobs

Interviews

Discussions

Minimum Size Subarray Sum

Medium

Asked by:

+11

More companies

98 views

Topics:

ArraysTwo PointersSliding Windows

Given an array of positive integers nums and a positive integer target, return the minimal length of a subarray whose sum is greater than or equal to target. If there is no such subarray, return 0 instead.

Example 1:

Input: target = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: The subarray [4,3] has the minimal length under the problem constraint.

Example 2:

Input: target = 4, nums = [1,4,4]
Output: 1

Example 3:

Input: target = 11, nums = [1,1,1,1,1,1,1,1]
Output: 0

Constraints:

1 <= target <= 10⁹
1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁴

Follow up: If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log(n)).

Try coding it in LeetCode

Minimum Size Subarray Sum

Medium

Asked by:

More companies

98 views

Topics:

ArraysTwo PointersSliding Windows

Example 1:

Input: target = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: The subarray [4,3] has the minimal length under the problem constraint.

Example 2:

Input: target = 4, nums = [1,4,4]
Output: 1

Example 3:

Input: target = 11, nums = [1,1,1,1,1,1,1,1]
Output: 0

Constraints:

1 <= target <= 10⁹
1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁴

Follow up: If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log(n)).

Try coding it in LeetCode

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:

Can the `nums` array contain zero values, and is it guaranteed that all integers will be positive, as stated in the problem description?
What are the possible ranges for the integers in the `nums` array and the `target` value? Is there a maximum size for the input array?
If there are multiple subarrays that meet the criteria with the same minimal length, is any one of them acceptable, or is there a specific subarray I should prefer (e.g., the one that appears earliest in the array)?
If no subarray sums up to at least the `target`, should I return 0 as mentioned in the problem description, or is there a different return value expected (e.g., -1, null, or an exception)?
Is the subarray required to be contiguous, meaning elements must be adjacent in the original `nums` array?

Brute Force Solution

Approach

The brute force method is about checking every single possibility to find the shortest segment that meets our goal. We'll examine every possible starting point and from there, try increasingly larger segments.

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

Start by looking at each number in the sequence one by one.
For each starting number, consider the segment that includes only that number and check if its sum is big enough.
If it's not, extend the segment to include the next number in the sequence and check again.
Keep extending the segment one number at a time, checking the sum each time.
If at any point the segment's sum is big enough, remember the size of that segment.
Do this for every possible starting number in the sequence.
Finally, compare all the segment sizes you remembered and choose the smallest one.

Code Implementation

def minimum_size_subarray_sum_brute_force(numbers, target_sum):
    minimum_window_size = float('inf')

    for window_start in range(len(numbers)):
        current_window_sum = 0
        for window_end in range(window_start, len(numbers)):
            current_window_sum += numbers[window_end]

            # Check if the current window sum meets the target.
            if current_window_sum >= target_sum:

                current_window_size = (window_end - window_start) + 1

                # We want to find the minimum size, update if necessary.
                if current_window_size < minimum_window_size:
                    minimum_window_size = current_window_size

                # Once a valid window is found, break inner loop.
                break

    # If no subarray is found, return 0
    if minimum_window_size == float('inf'):
        return 0

    return minimum_window_size

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through each of the n elements of the input array as a potential starting point for a subarray. For each starting element, the algorithm potentially iterates through the remaining elements to find a subarray whose sum is greater than or equal to the target. In the worst case, for each of the n starting points, we might iterate through nearly all n elements. This results in approximately n * n/2 operations. Therefore, the time complexity is O(n²).

Space Complexity

O(1) – The brute force algorithm, as described, iterates through the input array but does not create any auxiliary data structures that scale with the input size N (where N is the length of the input array). It only stores a few variables such as the current segment's sum, the minimum length found so far, the starting index of the segment, and the index of the current element being added to the segment. Therefore, the auxiliary space used is constant, regardless of the input size.

Optimal Solution

Approach

The key is to avoid checking every possible subarray. Instead, imagine two people moving along the numbers: one marking the start of a potential subarray, and the other marking the end. We cleverly adjust these two 'pointers' to find the smallest subarray that meets our target sum.

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

Start with both people at the beginning of the list of numbers.
Have the second person move forward, adding each number they pass to a running total.
Once the running total is greater than or equal to the target, record the length of the subarray between the two people.
Now, have the first person move forward, subtracting the numbers they pass from the running total. This effectively shrinks the subarray from the beginning.
Keep moving the first person forward as long as the running total is still greater than or equal to the target, and keep updating the shortest length found.
When the running total becomes less than the target, go back to moving the second person forward again, adding more numbers to the running total.
Repeat this process until the second person reaches the end of the list of numbers.
The shortest length you recorded during this process is the length of the minimum size subarray that meets the target sum.

Code Implementation

def find_min_subarray_sum(numbers, target):
    window_start = 0
    window_sum = 0
    min_length = float('inf')

    for window_end in range(len(numbers)):
        window_sum += numbers[window_end]

        # Shrink the window from the beginning until window_sum is smaller than target
        while window_sum >= target:
            min_length = min(min_length, window_end - window_start + 1)

            # Reduce window_sum as we shrink the window
            window_sum -= numbers[window_start]
            window_start += 1

    # If min_length was never updated, no subarray met the target sum
    if min_length == float('inf'):
        return 0
    else:
        return min_length

Big(O) Analysis

Time Complexity

O(n) – The algorithm uses two pointers, representing the start and end of a subarray. Each pointer moves from left to right across the input array of size n. The outer loop advances the 'end' pointer, and the inner loop (while loop) advances the 'start' pointer. Crucially, each pointer only moves forward and never goes back. Therefore, in the worst-case scenario, each pointer traverses the entire array once, resulting in a maximum of 2n operations. Consequently, the time complexity is O(n).

Space Complexity

O(1) – The provided algorithm utilizes a sliding window approach with two pointers. It maintains a running total of the numbers within the window. Only a few constant space variables like the two pointers, the running total, and the minimum length are used, regardless of the size N of the input array. Therefore, the auxiliary space complexity is constant.

Edge Cases

Case	How to Handle
Null or empty input array	Return 0 immediately as no subarray can be formed.
Array with a single element smaller than target	Return 0 because the target cannot be reached.
Array with a single element equal to or greater than the target	Return 1 as this single element forms a valid subarray.
All elements in the array are smaller than the target, and their sum is also smaller	Return 0, as no subarray will meet the condition.
Integer overflow when calculating the sum of a large subarray	Use a long data type for the sum to prevent overflow.
Target value is extremely large, and even the sum of all elements doesn't meet or exceed it	Return 0, indicating no valid subarray exists.
Array contains very large positive integers that can quickly exceed the target.	The sliding window approach will correctly handle this by shrinking the window when the sum exceeds the target.
All array elements are equal, and the target requires multiple elements to reach.	The algorithm should correctly calculate the minimum number of equal elements needed.

Null or empty input array

How to Handle:

Return 0 immediately as no subarray can be formed.

Array with a single element smaller than target

How to Handle:

Return 0 because the target cannot be reached.

Array with a single element equal to or greater than the target

How to Handle:

Return 1 as this single element forms a valid subarray.

All elements in the array are smaller than the target, and their sum is also smaller

How to Handle:

Return 0, as no subarray will meet the condition.

Integer overflow when calculating the sum of a large subarray

How to Handle:

Use a long data type for the sum to prevent overflow.

Target value is extremely large, and even the sum of all elements doesn't meet or exceed it

How to Handle:

Return 0, indicating no valid subarray exists.

Array contains very large positive integers that can quickly exceed the target.

How to Handle:

The sliding window approach will correctly handle this by shrinking the window when the sum exceeds the target.

All array elements are equal, and the target requires multiple elements to reach.

How to Handle:

The algorithm should correctly calculate the minimum number of equal elements needed.

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:

Can the `nums` array contain zero values, and is it guaranteed that all integers will be positive, as stated in the problem description?
What are the possible ranges for the integers in the `nums` array and the `target` value? Is there a maximum size for the input array?
If there are multiple subarrays that meet the criteria with the same minimal length, is any one of them acceptable, or is there a specific subarray I should prefer (e.g., the one that appears earliest in the array)?
If no subarray sums up to at least the `target`, should I return 0 as mentioned in the problem description, or is there a different return value expected (e.g., -1, null, or an exception)?
Is the subarray required to be contiguous, meaning elements must be adjacent in the original `nums` array?

Brute Force Solution

Approach

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

Start by looking at each number in the sequence one by one.
For each starting number, consider the segment that includes only that number and check if its sum is big enough.
If it's not, extend the segment to include the next number in the sequence and check again.
Keep extending the segment one number at a time, checking the sum each time.
If at any point the segment's sum is big enough, remember the size of that segment.
Do this for every possible starting number in the sequence.
Finally, compare all the segment sizes you remembered and choose the smallest one.

Code Implementation

def minimum_size_subarray_sum_brute_force(numbers, target_sum):
    minimum_window_size = float('inf')

    for window_start in range(len(numbers)):
        current_window_sum = 0
        for window_end in range(window_start, len(numbers)):
            current_window_sum += numbers[window_end]

            # Check if the current window sum meets the target.
            if current_window_sum >= target_sum:

                current_window_size = (window_end - window_start) + 1

                # We want to find the minimum size, update if necessary.
                if current_window_size < minimum_window_size:
                    minimum_window_size = current_window_size

                # Once a valid window is found, break inner loop.
                break

    # If no subarray is found, return 0
    if minimum_window_size == float('inf'):
        return 0

    return minimum_window_size

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Start with both people at the beginning of the list of numbers.
Have the second person move forward, adding each number they pass to a running total.
Once the running total is greater than or equal to the target, record the length of the subarray between the two people.
Now, have the first person move forward, subtracting the numbers they pass from the running total. This effectively shrinks the subarray from the beginning.
Keep moving the first person forward as long as the running total is still greater than or equal to the target, and keep updating the shortest length found.
When the running total becomes less than the target, go back to moving the second person forward again, adding more numbers to the running total.
Repeat this process until the second person reaches the end of the list of numbers.
The shortest length you recorded during this process is the length of the minimum size subarray that meets the target sum.

Code Implementation

def find_min_subarray_sum(numbers, target):
    window_start = 0
    window_sum = 0
    min_length = float('inf')

    for window_end in range(len(numbers)):
        window_sum += numbers[window_end]

        # Shrink the window from the beginning until window_sum is smaller than target
        while window_sum >= target:
            min_length = min(min_length, window_end - window_start + 1)

            # Reduce window_sum as we shrink the window
            window_sum -= numbers[window_start]
            window_start += 1

    # If min_length was never updated, no subarray met the target sum
    if min_length == float('inf'):
        return 0
    else:
        return min_length

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input array	Return 0 immediately as no subarray can be formed.
Array with a single element smaller than target	Return 0 because the target cannot be reached.
Array with a single element equal to or greater than the target	Return 1 as this single element forms a valid subarray.
All elements in the array are smaller than the target, and their sum is also smaller	Return 0, as no subarray will meet the condition.
Integer overflow when calculating the sum of a large subarray	Use a long data type for the sum to prevent overflow.
Target value is extremely large, and even the sum of all elements doesn't meet or exceed it	Return 0, indicating no valid subarray exists.
Array contains very large positive integers that can quickly exceed the target.	The sliding window approach will correctly handle this by shrinking the window when the sum exceeds the target.
All array elements are equal, and the target requires multiple elements to reach.	The algorithm should correctly calculate the minimum number of equal elements needed.

Null or empty input array

How to Handle:

Return 0 immediately as no subarray can be formed.

Array with a single element smaller than target

How to Handle:

Return 0 because the target cannot be reached.

Array with a single element equal to or greater than the target

How to Handle:

Return 1 as this single element forms a valid subarray.

All elements in the array are smaller than the target, and their sum is also smaller

How to Handle:

Return 0, as no subarray will meet the condition.

Integer overflow when calculating the sum of a large subarray

How to Handle:

Use a long data type for the sum to prevent overflow.

Target value is extremely large, and even the sum of all elements doesn't meet or exceed it

How to Handle:

Return 0, indicating no valid subarray exists.

Array contains very large positive integers that can quickly exceed the target.

How to Handle:

The sliding window approach will correctly handle this by shrinking the window when the sum exceeds the target.

All array elements are equal, and the target requires multiple elements to reach.

How to Handle:

The algorithm should correctly calculate the minimum number of equal elements needed.