Similar Problems

Similar Problems not available

Minimum Size Subarray Sum - Leetcode Solution

LeetCode:  Minimum Size Subarray Sum Leetcode Solution

Difficulty: Medium

Topics: sliding-window prefix-sum binary-search array  


Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there isn't one, return 0 instead.

Example 1:

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

Example 2:

Input: s = 15, nums = [1,2,3,4,5] Output: 5


The given problem can be solved efficiently using the sliding window technique. The approach is to start with a window of size 1 and keep on increasing its size until the sum of its elements is greater than or equal to the given target sum s. When the sum becomes greater than or equal to the target, we try to minimize the window size by moving the left pointer until the sum becomes less than the target again. This way, we try to find the shortest possible subarray that adds up to the target sum.

The steps to the approach can be listed as follows:

  1. Initialize two pointers left and right to the first element of the array.
  2. Initialize a variable "sum" to be the sum of the first element, i.e., nums[0].
  3. Initialize a variable "minlen" to a value larger than the size of the array, say n+1, as the length of the shortest subarray is less than or equal to the length of the array.
  4. Loop through the array until the right pointer reaches the end of the array: a. Add the value of nums[right] to sum. b. If the sum becomes greater than or equal to the target sum s: i. Update the value of minlen to be the minimum of minlen and (right-left+1). ii. Keep moving the left pointer to the right until the sum becomes less than the target sum s. c. Increment the right pointer.
  5. Return minlen.

The time complexity of this approach is O(n), where n is the size of the input array, as we loop through the array only once. The space complexity is O(1) as we use only a few variables.

Here's the Python code for the solution:

def minSubArrayLen(s, nums): n = len(nums) left, right, sum, minlen = 0, 0, nums[0], n+1 while right < n: if sum >= s: minlen = min(minlen, right-left+1) sum -= nums[left] left += 1 else: right += 1 if right < n: sum += nums[right] return minlen if minlen <= n else 0


print(minSubArrayLen(7, [2,3,1,2,4,3])) # Output: 2 print(minSubArrayLen(15, [1,2,3,4,5])) # Output: 5

This will print the output as mentioned in the examples.

Minimum Size Subarray Sum Solution Code