Shortest subarray length

January 9, 2024

Problem #

Given an array of integers nums and a target value k, find the length of the shortest subarray whose sum is greater than or equal to k.

Solution #

Steps:

1. Initialize two pointers, left and right, both at the beginning of the array.
2. Initialize a variable current_sum to 0.
3. Iterate while right is within the bounds of the array:
   • Add nums[right] to current_sum.
   • While current_sum is greater than or equal to k:
     • Update the minimum length if needed: min_length = min(min_length, right - left + 1).
     • Subtract nums[left] from current_sum.
     • Move left to the right.
   • Move right to the right.
4. Return min_length (or a large value if no subarray meets the criteria).

Time Complexity #

O(n), where n is the length of the array.

Space Complexity #

O(1), as we only use a constant amount of extra space.

Example #

def shortest_subarray_with_sum(nums, k):
    min_length = float('inf')
    current_sum = 0
    left = 0

    for right in range(len(nums)):
        current_sum += nums[right]

        while current_sum >= k:
            min_length = min(min_length, right - left + 1)
            current_sum -= nums[left]
            left += 1

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