[Array + Two Pointers] LC 209. Minimum Size Subarray Sum

  • Given an array of positive integers
  • minimal length of a contiguous subarray [numsl, numsl+1, ..., numsr-1, numsr] of which the sum is greater than or equal to target
  • *Greedy or Sorting is not allowed!
  • Iterate through the array and add each element to the sum, one at the time
  • During each iteration, we can keep subtracting the numbers (from sum) from the left until it < target
  • classic two pointers
  • concept of sliding & shrinking the left window (usually a while loop)
  • Time: O(N) → as we iterate the array once
  • Space: O(1) → didn’t occupy any extra space by creating additional data structures
class Solution(object):
def minSubArrayLen(self, target, nums):
"""
:type target: int
:type nums: List[int]
:rtype: int"""

n = len(nums)
ans = 1000000
left = 0
result = 0
for i in range(n):
result+=nums[i]
while result >= target:
ans = min(ans, i+1-left)

result-=nums[left]
left+=1

if ans != 1000000:
return ans
else:
return 0

--

--

--

Data Engineering & Analytics

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

Recommended from Medium

Continuous Deployment for publishing NPM packages

Introducing Postlight’s WordPress + React Starter Kit

Getting started with js-csp — part 2

Welcome To JavaScript.

Omit Is Being Removed in Lodash 5

Understanding the this on Javascript

Hello World

Updating Redux to 2021 (Functional vs Class Components)

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
Iris S

Iris S

Data Engineering & Analytics

More from Medium

Job search update and NPM Packages

A filter lense 17/01/2022 2:27 Yerevan Time

Minimum Spanning Tree — Kruskal Algorithm

Should the ‘Number of People Trained’ Be Part of Communicating Impact?