Shortest Subarray With Sum At Least K - Leetcode Solution

Problem statement:

Given an array nums of integers 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.

Example:

Input: nums = [2,-1,2], k = 3 Output: 3

Input: nums = [1,-1,4,-2,5], k = 3 Output: 2

Solution approach:

This problem could be resolved by simple two-pointer approach. Let's define two pointers "left" and "right" and at the start point they both should be zero. Also, initialize the current sum "curr_sum" to zero. First, move the right pointer to the first valid index where the sum from "left" to "right" could be greater than or equal to "k". Here we will add the value of "nums[right]" in "curr_sum". After that, we keep moving the right pointer until the sum exceeds "k" and also storing the minimum sub-array length encountered so far. Then, we will move the left pointer forward by one and if the left pointer crosses the right pointer, we will move the right one to the next position and reset the "curr_sum" to zero.

The above steps should be repeated until the right pointer reaches the end index of the array.

Algorithms:

Algorithm 1:

1. Intitialize the current sum "curr_sum" to zero, left pointer to zero and right pointer to zero.
2. Define a variable "min_len" and initialized it to the maximum integer value.
3. Run a loop until the right pointer reaches the end index of the array. a) If "curr_sum" is less than the target sum "k", move the right pointer forward and add "nums[right]" to "curr_sum". b) Else, if "curr_sum" is greater than or equal to "k", update "min_len" as the minimum value of "min_len" and the difference between right and left pointers and subtract "nums[left]" from the "curr_sum". Move the left pointer forward by one position. c) Continue the loop until the right pointer reaches the end index of the array.
4. Check whether "min_len" is the maximum integer value, if yes, then return -1. Else, return "min_len".

Algorithm 2:

1. Define a map "seen" to keep track of the partial sums and their respective indices in "nums".
2. Initialize the current sum "curr_sum" to zero and define a variable "min_len" and initialized it to the maximum integer value.
3. Run a loop until the end index of array. a) Keep adding "nums[i]" to the "curr_sum". b) If "curr_sum" is less than the target sum "k", ignore the current iteration. c) Else, check whether "curr_sum" - "k" is in the "seen" map, if yes, then update the "min_len" as the minimum value of "min_len" and the difference between current index and the index of ("curr_sum" - "k") in "seen". d) Add the "curr_sum" and the current index "i" to the "seen" map if they are not already present.
4. Check whether "min_len" is the maximum integer value, if yes, then return -1. Else, return "min_len".

Time complexity:

Algorithm 1: O(n) Algorithm 2: O(n*logn)

Space complexity:

Algorithm 1: O(1) Algorithm 2: O(n)

The desired solution in python:

Algorithm 1:

def shortestSubarray(nums: List[int], k: int) -> int: n = len(nums) left = 0 right = 0 curr_sum = 0 min_len = float('inf') while right < n: while right < n and curr_sum < k: curr_sum += nums[right] right += 1 while left < right and curr_sum >= k: min_len = min(min_len, right - left) curr_sum -= nums[left] left += 1 return min_len if min_len != float('inf') else -1

Algorithm 2:

def shortestSubarray(nums: List[int], k: int) -> int: n = len(nums) curr_sum = 0 seen = {0 : -1} min_len = float('inf') for i in range(n): curr_sum += nums[i] if curr_sum - k in seen: min_len = min(min_len, i - seen[curr_sum - k]) seen.setdefault(curr_sum, i) return min_len if min_len != float('inf') else -1

I hope this solution will help you.

1