Brute Force Solution

The most straightforward approach is to check all possible subarrays and find the shortest one with a sum of at least k. This involves two nested loops to define the start and end indices of the subarray, and an inner loop (or a sum calculation within the outer loops) to compute the sum of the subarray. This is not the optimal solution, but it's good to start with to understand the problem.

Algorithm:

1. Iterate through all possible start indices i from 0 to n-1.
2. For each start index i, iterate through all possible end indices j from i to n-1.
3. Calculate the sum of the subarray nums[i...j].
4. If the sum is at least k, update the minimum length if the current subarray's length is smaller.
5. If no subarray with a sum of at least k is found, return -1.

Code Example (Python):

def shortest_subarray_brute_force(nums, k):
    n = len(nums)
    min_length = float('inf')

    for i in range(n):
        for j in range(i, n):
            subarray_sum = sum(nums[i:j+1])
            if subarray_sum >= k:
                min_length = min(min_length, j - i + 1)

    if min_length == float('inf'):
        return -1
    else:
        return min_length

Time Complexity: O(n^3), where n is the length of the input array. The nested loops take O(n^2) time, and the sum calculation inside the loops takes O(n) time in the worst case.

Space Complexity: O(1). We only use a few variables to store the minimum length and the subarray sum.

Optimal Solution: Sliding Window with Monotonic Queue

A more efficient approach uses a sliding window technique combined with a monotonic queue (deque). The idea is to maintain a queue of prefix sums, where the queue is monotonically increasing. This allows us to efficiently find the shortest subarray with a sum of at least k.

Algorithm:

1. Compute the prefix sums of the array nums. Let prefix_sum[i] be the sum of nums[0...i-1]. prefix_sum[0] is 0.
2. Initialize a deque (double-ended queue) to store indices of the prefix sums.
3. Iterate through the prefix sums:
   • While the deque is not empty and the current prefix sum minus the prefix sum at the front of the deque is at least k, update the minimum length and remove the front element from the deque. This step shrinks the window from the left.
   • While the deque is not empty and the current prefix sum is less than or equal to the prefix sum at the back of the deque, remove the back element from the deque. This maintains the monotonic property of the queue.
   • Add the current index to the back of the deque.
4. If no subarray with a sum of at least k is found, return -1.

Code Example (Python):

from collections import deque

def shortest_subarray(nums, k):
    n = len(nums)
    prefix_sum = [0] * (n + 1)
    for i in range(n):
        prefix_sum[i + 1] = prefix_sum[i] + nums[i]

    min_length = float('inf')
    deque_indices = deque()

    for i in range(n + 1):
        while deque_indices and prefix_sum[i] - prefix_sum[deque_indices[0]] >= k:
            min_length = min(min_length, i - deque_indices.popleft())
        while deque_indices and prefix_sum[i] <= prefix_sum[deque_indices[-1]]:
            deque_indices.pop()
        deque_indices.append(i)

    if min_length == float('inf'):
        return -1
    else:
        return min_length

Time Complexity: O(n), where n is the length of the input array. Each element is added and removed from the deque at most once.

Space Complexity: O(n), where n is the length of the input array. The prefix sum array and the deque can store at most n elements.

Edge Cases:

• Empty array: The problem statement specifies that the input array is non-empty, so we don't need to handle this case explicitly.
• No subarray with sum >= k: The algorithm returns -1 if no such subarray exists.
• Negative numbers: The presence of negative numbers in the input array is handled correctly by the prefix sum and sliding window approach. The monotonic queue ensures that we always consider the shortest possible subarray that meets the sum requirement, even with negative numbers.
• k = 0: if k = 0, then any empty subarray has sum greater than or equal to k. In this situation, the question asks for a non-empty subarray, so we can find the first non-negative number's index.