Minimum Size Subarray Sum

Given an array of positive integers nums and a positive integer target, return the minimal length of a contiguous subarray [numsl, numsl+1, ..., numsr-1, numsr] of which the sum is greater than or equal to target. If there is no such subarray, return 0 instead.

Example 1:

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

Example 2:

Input: target = 4, nums = [1,4,4]
Output: 1

Example 3:

Input: target = 11, nums = [1,1,1,1,1,1,1,1]
Output: 0

Constraints:

  • 1 <= target <= 109
  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 105

Implementation:

We could keep 2 pointers ,one for the start and another for the end of the current subarray, and make optimal moves so as to keep the sum greater than s as well as maintain the lowest size possible.

Algorithm

  • Initialize left pointer to 0 and sum to 0
  • Iterate over the nums:
  • Add nums[i] to sum.
  • While sum is greater than or equal to s:
  • Update result=min(result,i+1−left), where i+1−left is the size of current subarray.
  • It means that the first index can safely be incremented, since, the minimum subarray starting with this index with sum≥s has been achieved
  • Subtract nums[left] from sum and increment left.

Complexity analysis

  • Time complexity: O(n). Single iteration .
  • Space complexity: O(1) extra space.

If you like the content please follow me here @medium and at LinkedIn

https://www.linkedin.com/in/jaydeep-shil-75a90847

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store