Jobs

Interviews

Discussions

Shortest Subarray with Sum at Least K

Hard

Google

1 view

Topics:

ArraysSliding Windows

Given an integer array nums and an integer k, return the length of the shortest non-empty subarray of nums with a sum of at least k. If there is no such subarray, return -1.

A subarray is a contiguous part of an array.

For example:

nums = [1], k = 1. The output should be 1 because the subarray [1] has a sum of 1, which is at least k=1, and the length is 1.
nums = [1, 2], k = 4. The output should be -1 because no subarray has a sum of at least 4.
nums = [2, -1, 2], k = 3. The output should be 3 because the shortest subarray with a sum of at least 3 is the entire array [2, -1, 2], which has a length of 3.

Write a function to efficiently find the length of the shortest subarray with a sum of at least k.

Shortest Subarray with Sum at Least K

Hard

Google

1 view

Topics:

ArraysSliding Windows

Given an integer array nums and an integer k, return the length of the shortest non-empty subarray of nums with a sum of at least k. If there is no such subarray, return -1.

A subarray is a contiguous part of an array.

For example:

nums = [1], k = 1. The output should be 1 because the subarray [1] has a sum of 1, which is at least k=1, and the length is 1.
nums = [1, 2], k = 4. The output should be -1 because no subarray has a sum of at least 4.
nums = [2, -1, 2], k = 3. The output should be 3 because the shortest subarray with a sum of at least 3 is the entire array [2, -1, 2], which has a length of 3.

Write a function to efficiently find the length of the shortest subarray with a sum of at least k.

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 are the possible ranges for the values in the `nums` array, and what is the range for the integer `k`? Can they be negative, zero, or very large?
What should I return if the input array `nums` is null or empty?
If there are multiple subarrays with a sum at least `k`, should I return the length of *any* shortest subarray, or is there a specific shortest subarray I need to identify based on some criteria (e.g., the one that appears first in the array)?
Can you provide an example input array `nums` and integer `k` where the shortest subarray with a sum at least `k` is longer than 1?
What is the expected behavior if the sum of all the elements in `nums` is less than `k`? Should I still return -1?

Brute Force Solution

Approach

The brute force method for finding the shortest part of a collection of numbers that adds up to at least a certain target value is simple. We look at every possible part, check if it meets the criteria, and remember the smallest one that does. We explore all options without trying to be smart about it.

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

First, consider just the first number in the collection alone. Does it meet the target value?
Then, consider the first two numbers together. Does their sum meet the target value?
Continue this pattern, adding one more number from the beginning each time, until you've considered all the numbers from the beginning.
Next, start from the second number in the collection, and repeat the same process. Consider the second number alone, then the second and third numbers together, and so on.
Keep shifting the starting point one number over each time, repeating the process of considering progressively larger sections until you've checked every possible section of numbers.
As you check each section, see if its sum is at least the target value. If it is, write down the size (number of numbers in that section).
Finally, after checking every possible section, look at all the sizes you wrote down. The smallest one is the length of the shortest section that meets the target value.

Code Implementation

def shortest_subarray_with_sum_at_least_k_brute_force(numbers, target):
    minimum_length = float('inf')

    # Iterate through all possible start indices
    for start_index in range(len(numbers)): 
        current_sum = 0

        # Iterate through all possible end indices starting from the start index
        for end_index in range(start_index, len(numbers)): 
            current_sum += numbers[end_index]

            # Check if the current subarray sum meets the target
            if current_sum >= target:

                #Update min length if current subarray is shorter
                subarray_length = end_index - start_index + 1
                minimum_length = min(minimum_length, subarray_length)

    # If no subarray meets the target, return -1
    if minimum_length == float('inf'):
        return -1

    return minimum_length

Big(O) Analysis

Time Complexity

O(n²) – The provided brute force approach considers all possible subarrays. For an array of size n, the outer loop iterates n times, defining the starting point of the subarray. The inner loop, for each starting point, iterates up to n times to define the end point of the subarray. Therefore, we have nested loops where each loop's iterations are dependent on the size of the input array n. This leads to approximately n * n/2 comparisons, which simplifies to O(n²).

Space Complexity

O(1) – The provided brute force algorithm iterates through all possible subarrays of the input array but only stores the minimum length found so far. It does not use any auxiliary data structures that grow with the input size N (the number of elements in the input array). The algorithm only needs a few variables to store the current subarray's sum, start and end indices, and the minimum length, which require constant space.

Optimal Solution

Approach

We want to find the shortest continuous section that adds up to at least a certain number. The trick is to keep track of possible starting points for our section using a special list that helps us quickly find the best start.

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

First, calculate a running total of all the numbers up to each point.
Create an empty list to keep track of potentially good starting points for our section.
Go through each running total, one by one.
While our list isn't empty and the current running total minus the running total at the front of our list is greater than or equal to our target, we have a valid section. Calculate the length of this section and update our shortest length if necessary. Then, remove the first element from the list, because we have found the best shortest length subarray.
While our list isn't empty and the running total at the end of our list is greater than or equal to the current running total, remove the last element from the list. This ensures that our list only contains useful starting points.
Add the current position to the end of our list.
After going through all the running totals, return the shortest length we found. If we didn't find any valid section, return -1.

Code Implementation

def shortest_subarray_with_sum_at_least_k(numbers, k_value):
    prefix_sums = [0] * (len(numbers) + 1)
    for i in range(len(numbers)):
        prefix_sums[i+1] = prefix_sums[i] + numbers[i]

    shortest_length = float('inf')
    monotonic_queue = []

    for i in range(len(prefix_sums)):
        # Check for valid subarrays, removing from the front if possible
        while monotonic_queue and prefix_sums[i] - prefix_sums[monotonic_queue[0]] >= k_value:

            shortest_length = min(shortest_length, i - monotonic_queue[0])
            monotonic_queue.pop(0)

        # Maintain a decreasing prefix sum queue
        while monotonic_queue and prefix_sums[monotonic_queue[-1]] >= prefix_sums[i]:

            monotonic_queue.pop()

        monotonic_queue.append(i)

    if shortest_length == float('inf'):
        return -1
    return shortest_length

Big(O) Analysis

Time Complexity

O(n) – The primary loop iterates through the prefix sums array once, which takes O(n) time, where n is the length of the input array. The while loops inside this main loop, although nested, each perform at most one operation per element because each index can be added to and removed from the deque only once. Therefore, the while loops' operations are amortized O(n). Consequently, the overall time complexity is dominated by the single pass through the array, making it O(n).

Space Complexity

O(N) – The primary contributor to the space complexity is the list used to keep track of potentially good starting points. In the worst-case scenario, this list could store indices for all prefixes of the input array, leading to a maximum size proportional to N, where N is the number of elements in the input array. Therefore, the auxiliary space used is O(N).

Edge Cases

Case	How to Handle
Empty input array (nums is null or has length 0)	Return -1 immediately, as there's no subarray to evaluate.
Array with one element, where the element is >= k	Return 1, as a single element subarray satisfies the condition.
Array with one element, where the element is < k	Return -1, as no subarray can satisfy the condition.
Array contains only negative numbers, and the sum of all elements is < k	Return -1, as no positive sum can be achieved.
Array contains a mix of positive and negative numbers, with a very large negative number that drastically reduces the running sum	The sliding window or prefix sum approach will correctly handle large negative numbers by shrinking the window or discarding prefixes that reduce the sum below a certain threshold.
All elements in the array are zero, and k > 0	Return -1, as no positive sum can be achieved.
All elements in the array are zero, and k <= 0	Return 1, as a single zero element subarray satisfies the condition.
Integer overflow in prefix sum calculation when nums contains large positive numbers and the array is large	Use long data type for prefix sums to prevent overflow.

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 are the possible ranges for the values in the `nums` array, and what is the range for the integer `k`? Can they be negative, zero, or very large?
What should I return if the input array `nums` is null or empty?
If there are multiple subarrays with a sum at least `k`, should I return the length of *any* shortest subarray, or is there a specific shortest subarray I need to identify based on some criteria (e.g., the one that appears first in the array)?
Can you provide an example input array `nums` and integer `k` where the shortest subarray with a sum at least `k` is longer than 1?
What is the expected behavior if the sum of all the elements in `nums` is less than `k`? Should I still return -1?

Brute Force Solution

Approach

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

First, consider just the first number in the collection alone. Does it meet the target value?
Then, consider the first two numbers together. Does their sum meet the target value?
Continue this pattern, adding one more number from the beginning each time, until you've considered all the numbers from the beginning.
Next, start from the second number in the collection, and repeat the same process. Consider the second number alone, then the second and third numbers together, and so on.
Keep shifting the starting point one number over each time, repeating the process of considering progressively larger sections until you've checked every possible section of numbers.
As you check each section, see if its sum is at least the target value. If it is, write down the size (number of numbers in that section).
Finally, after checking every possible section, look at all the sizes you wrote down. The smallest one is the length of the shortest section that meets the target value.

Code Implementation

def shortest_subarray_with_sum_at_least_k_brute_force(numbers, target):
    minimum_length = float('inf')

    # Iterate through all possible start indices
    for start_index in range(len(numbers)): 
        current_sum = 0

        # Iterate through all possible end indices starting from the start index
        for end_index in range(start_index, len(numbers)): 
            current_sum += numbers[end_index]

            # Check if the current subarray sum meets the target
            if current_sum >= target:

                #Update min length if current subarray is shorter
                subarray_length = end_index - start_index + 1
                minimum_length = min(minimum_length, subarray_length)

    # If no subarray meets the target, return -1
    if minimum_length == float('inf'):
        return -1

    return minimum_length

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

First, calculate a running total of all the numbers up to each point.
Create an empty list to keep track of potentially good starting points for our section.
Go through each running total, one by one.
While our list isn't empty and the current running total minus the running total at the front of our list is greater than or equal to our target, we have a valid section. Calculate the length of this section and update our shortest length if necessary. Then, remove the first element from the list, because we have found the best shortest length subarray.
While our list isn't empty and the running total at the end of our list is greater than or equal to the current running total, remove the last element from the list. This ensures that our list only contains useful starting points.
Add the current position to the end of our list.
After going through all the running totals, return the shortest length we found. If we didn't find any valid section, return -1.

Code Implementation

def shortest_subarray_with_sum_at_least_k(numbers, k_value):
    prefix_sums = [0] * (len(numbers) + 1)
    for i in range(len(numbers)):
        prefix_sums[i+1] = prefix_sums[i] + numbers[i]

    shortest_length = float('inf')
    monotonic_queue = []

    for i in range(len(prefix_sums)):
        # Check for valid subarrays, removing from the front if possible
        while monotonic_queue and prefix_sums[i] - prefix_sums[monotonic_queue[0]] >= k_value:

            shortest_length = min(shortest_length, i - monotonic_queue[0])
            monotonic_queue.pop(0)

        # Maintain a decreasing prefix sum queue
        while monotonic_queue and prefix_sums[monotonic_queue[-1]] >= prefix_sums[i]:

            monotonic_queue.pop()

        monotonic_queue.append(i)

    if shortest_length == float('inf'):
        return -1
    return shortest_length

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty input array (nums is null or has length 0)	Return -1 immediately, as there's no subarray to evaluate.
Array with one element, where the element is >= k	Return 1, as a single element subarray satisfies the condition.
Array with one element, where the element is < k	Return -1, as no subarray can satisfy the condition.
Array contains only negative numbers, and the sum of all elements is < k	Return -1, as no positive sum can be achieved.
Array contains a mix of positive and negative numbers, with a very large negative number that drastically reduces the running sum	The sliding window or prefix sum approach will correctly handle large negative numbers by shrinking the window or discarding prefixes that reduce the sum below a certain threshold.
All elements in the array are zero, and k > 0	Return -1, as no positive sum can be achieved.
All elements in the array are zero, and k <= 0	Return 1, as a single zero element subarray satisfies the condition.
Integer overflow in prefix sum calculation when nums contains large positive numbers and the array is large	Use long data type for prefix sums to prevent overflow.