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: 


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

Follow up:

If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log n).

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: Data structures

Sorting

Amortized analysis

Range queries

Starter code: class Solution:
    def minSubArrayLen(self, s: int, nums: List[int]) -> int:
        

Solutions:
class Solution:

	def minSubArrayLen(self, k, nums):
		if not nums:
			return 0
		_min = float('inf')
		_sum = 0
		j = 0
		for (i, n) in enumerate(nums):
			_sum += n
			while _sum >= k:
				_min = min(i - j + 1, _min)
				_sum -= nums[j]
				j += 1
		return _min if _min != float('inf') else 0


class Solution:

	def minSubArrayLen(self, s, nums):
		result = float('inf')
		left = 0
		total = 0
		for i in range(len(nums)):
			total += nums[i]
			while total >= s:
				result = min(result, i + 1 - left)
				total -= nums[left]
				left += 1
		return 0 if result == float('inf') else result


class Solution:

	def minSubArrayLen(self, s, nums):
		(left, right, curr) = (0, 0, 0)
		minLen = len(nums) + 1
		while right < len(nums):
			curr += nums[right]
			while curr >= s:
				minLen = min(minLen, right - left + 1)
				curr -= nums[left]
				left += 1
			right += 1
		return minLen if minLen != len(nums) + 1 else 0


class Solution:

	def minSubArrayLen(self, s, nums):
		i = 0
		j = 0
		_s = 0
		_min = len(nums) + 1
		if len(nums) == 0:
			return 0
		while j < len(nums):
			_s += nums[j]
			j += 1
			while _s >= s:
				_min = min(_min, j - i)
				_s -= nums[i]
				i += 1
		if _min > len(nums):
			return 0
		else:
			return _min


class Solution:

	def minSubArrayLen(self, s, nums):
		total = left = 0
		result = len(nums) + 1
		for (right, n) in enumerate(nums):
			total += n
			while total >= s:
				result = min(result, right - left + 1)
				total -= nums[left]
				left += 1
		return result if result <= len(nums) else 0


class Solution:

	def minSubArrayLen(self, s, nums):
		if sum(nums) < s:
			return 0
		res = float('inf')
		start = 0
		curr = 0
		for i in range(len(nums)):
			curr += nums[i]
			while curr >= s:
				res = min(res, i - start + 1)
				curr -= nums[start]
				start += 1
		return res


class Solution:

	def minSubArrayLen(self, s, nums):
		if not nums or sum(nums) < s:
			return 0
		ans = len(nums)
		left = 0
		temps = 0
		for i in range(len(nums)):
			temps += nums[i]
			while temps >= s:
				ans = min(ans, i + 1 - left)
				temps -= nums[left]
				left += 1
		return ans


class Solution:

	def minSubArrayLen(self, s, nums):
		i = 0
		j = 0
		tempSum = 0
		length = len(nums)
		minLength = 2147483647
		while i < length and j < length:
			while j < length:
				tempSum += nums[j]
				if tempSum >= s:
					break
				j += 1
			if j < length:
				minLength = min(j - i + 1, minLength)
				while i <= j:
					if tempSum < s:
						break
					tempSum -= nums[i]
					i += 1
				minLength = min(j - i + 2, minLength)
				j += 1
		if minLength == 2147483647:
			return 0
		else:
			return minLength


class Solution(object):

	def minSubArrayLen(self, s, nums):
		if not nums:
			return 0
		import math
		minlen = math.inf
		pt1 = 0
		pt2 = 0
		cursum = nums[0]
		while pt2 < len(nums):
			if cursum >= s:
				minlen = min(minlen, pt2 - pt1 + 1)
			if minlen == 1:
				return 1
			if cursum < s:
				pt2 += 1
				if pt2 < len(nums):
					cursum += nums[pt2]
			elif cursum >= s:
				cursum -= nums[pt1]
				pt1 += 1
		return 0 if minlen == math.inf else minlen


class Solution:

	def minSubArrayLen(self, s, nums):
		prePtr = 0
		curPtr = 0
		curSum = 0
		res = float('inf')
		while curPtr < len(nums):
			curSum += nums[curPtr]
			if curSum >= s:
				while curSum >= s:
					curSum -= nums[prePtr]
					prePtr += 1
				prePtr -= 1
				curSum += nums[prePtr]
				res = min(res, curPtr - prePtr + 1)
			curPtr += 1
		if res == float('inf'):
			return 0
		else:
			return res


class Solution:

	def minSubArrayLen(self, s, nums):
		if nums is None or len(nums) == 0:
			return 0
		running_sum = [nums[0]]
		for num in nums[1:]:
			running_sum.append(running_sum[-1] + num)

		def sub_sum(i, j):
			to_remove = 0 if i == 0 else running_sum[i - 1]
			to_add = 0 if j == 0 else running_sum[j - 1]
			return to_add - to_remove
		min_seen = float('inf')
		fast = 0
		slow = 0
		while fast < len(nums):
			while sub_sum(slow, fast) < s and fast < len(nums):
				fast += 1
			while sub_sum(slow, fast) >= s and slow <= fast:
				min_seen = min(min_seen, fast - slow)
				slow += 1
		return 0 if min_seen == float('inf') else min_seen