Minimum Size Subarray Sum

Photo by kofookoo.de on Unsplash

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

--

--

--

Full Stack Programmer, love to solve problem’s during free time.

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Track, log, and measure your Unsplash photo stats for greater future insight

Behind the scene look at the Unsplash stats page for my profile

Understanding Data Science Concepts using Insightful Images

Trading Plan: 15 March 2022

Convert Pivot Table results into Formulas

Eight Things Cities Can Do Today to Generate Evidence and Outcomes

Pandas III: value_counts(), duplicated(), min(), max()

Different Factors that Impact Weekly Working Hours

Data Profiling — Command Line Tools

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
Jaydeep

Jaydeep

Full Stack Programmer, love to solve problem’s during free time.

More from Medium

Rapper Lil Carter Talks About Fortnite & New Music With Medium — Stephen Best

ARTS Week 20

98. Validate Binary Search Tree

Two sum Leetcode problem solution