Given an array of integers (A[])  and a number x, find the smallest subarray with sum greater than the given value. If such a subarray do not exist return 0 in that case.
Note: The answer always exists. It is guaranteed that x doesn't exceed the summation of a[i] (from 1 to N).
Example 1:
Input:
A[] = {1, 4, 45, 6, 0, 19}
x  =  51
Output: 3
Explanation:
Minimum length subarray is 
{4, 45, 6}
Example 2:
Input:
A[] = {1, 10, 5, 2, 7}
   x  = 9
Output: 1
Explanation:
Minimum length subarray is {10}
 
Your Task:  
You don't need to read input or print anything. Your task is to complete the function smallestSubWithSum() which takes the array A[], its size N and an integer X as inputs and returns the required ouput.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ N, x ≤ 10^{5}
1 ≤ A[] ≤ 10^{4}

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Starter code: class Solution:

    def smallestSubWithSum(self, a, n, x):

        # Your code goes here 

        



Solutions:
class Solution:

	def smallestSubWithSum(self, a, n, x):
		start = 0
		end = 1
		s = a[start]
		ans = n + 1
		if s > x:
			return 1
		if end < n:
			s += a[end]
		while start < n and end < n:
			if s > x:
				ans = min(ans, end - start + 1)
				s -= a[start]
				start += 1
			else:
				end += 1
				if end < n:
					s += a[end]
		return ans


class Solution:

	def smallestSubWithSum(self, a, n, x):
		i = 0
		j = 0
		s = 0
		mini = float('inf')
		while i < n:
			if a[j] > x:
				return 1
			s += a[j]
			if s > x:
				while i < j:
					if s - a[i] <= x:
						mini = min(mini, j - i + 1)
						break
					s -= a[i]
					i += 1
			j += 1
			if j >= n:
				break
		return mini


import sys

class Solution:

	def smallestSubWithSum(self, a, n, x):
		(i, j, curr_sum, ans) = (0, 0, 0, sys.maxsize)
		while j < n:
			curr_sum += a[j]
			if curr_sum < x:
				j += 1
			elif curr_sum > x:
				while curr_sum > x:
					ans = min(ans, j - i + 1)
					curr_sum -= a[i]
					i += 1
				j += 1
			elif curr_sum == x:
				j += 1
		return ans


class Solution:

	def smallestSubWithSum(self, a, n, x):
		currentSum = 0
		startIndex = 0
		endIndex = -1
		minLength = n
		for i in range(len(a)):
			endIndex = i
			currentSum += a[i]
			while currentSum > x:
				if currentSum - a[startIndex] <= x:
					break
				currentSum -= a[startIndex]
				startIndex += 1
			if currentSum > x:
				currentMin = endIndex - startIndex + 1
				if currentMin < minLength:
					minLength = currentMin
		if startIndex > endIndex:
			return 0
		return minLength


class Solution:

	def smallestSubWithSum(self, a, n, x):
		ans = []
		l = 0
		r = 1
		su = a[l]
		while l < r:
			if su <= x:
				if r >= len(a):
					break
				su += a[r]
				r += 1
			elif su > x:
				su -= a[l]
				ans.append(r - l)
				l += 1
		return min(ans)


import sys

class Solution:

	def smallestSubWithSum(self, arr, n, x):
		i = 0
		j = 0
		mini = 10 ** 9
		sum = 0
		while i < n or sum > x:
			if i < n and sum <= x:
				sum += arr[i]
				i = i + 1
			else:
				ini = i - j
				if ini < mini:
					mini = ini
				sum = sum - arr[j]
				j = j + 1
		return mini


class Solution:

	def smallestSubWithSum(self, a, n, x):
		l = 0
		r = 1
		size = n + 1
		sum = a[0]
		if sum > x:
			return 1
		if r < n:
			sum += a[r]
		while l < n and r < n:
			if x > sum or x == sum:
				r += 1
				if r < n:
					sum += a[r]
			elif sum > x:
				size = min(size, r - l + 1)
				sum -= a[l]
				l += 1
		return size


class Solution:

	def smallestSubWithSum(self, a, n, x):
		curr_sum = 0
		min_len = n + 1
		start = 0
		end = 0
		while end < n:
			while curr_sum <= x and end < n:
				curr_sum += a[end]
				end += 1
			while curr_sum > x and start < n:
				if end - start < min_len:
					min_len = end - start
				curr_sum -= a[start]
				start += 1
		return min_len


class Solution:

	def smallestSubWithSum(self, nums, n, target):
		if not nums:
			return 0
		(l, r) = (0, 0)
		res = float('inf')
		cur = 0
		while r < len(nums):
			cur += nums[r]
			r += 1
			while cur > target:
				cur -= nums[l]
				l += 1
				res = min(res, r - l + 1)
		return res if res != float('inf') else 0


import sys

class Solution:

	def smallestSubWithSum(self, a, n, x):
		start = 0
		end = 1
		result = sys.maxsize - 1
		sum = a[0]
		if sum > x:
			return 1
		if end < n:
			sum += a[end]
		while start < n and end < n:
			if sum > x:
				result = min(result, end - start + 1)
				sum -= a[start]
				start += 1
			else:
				end += 1
				if end < n:
					sum += a[end]
		return result


class Solution:

	def smallestSubWithSum(self, a, n, x):
		start = 0
		pointer = 0
		sum = 0
		result = []
		for i in range(len(a)):
			pointer = i
			sum += a[pointer]
			if sum >= x:
				while sum - a[start] > x:
					sum -= a[start]
					start += 1
				result.append(pointer - start + 1)
				sum -= a[start]
				start += 1
		return min(result)


class Solution:

	def smallestSubWithSum(self, a, n, x):
		(res, window_start, window_sum) = (float('inf'), 0, 0)
		for window_end in range(len(a)):
			window_sum += a[window_end]
			while window_sum > x:
				res = min(res, window_end - window_start + 1)
				window_sum -= a[window_start]
				window_start += 1
		return 0 if res == float('inf') else res


class Solution:

	def smallestSubWithSum(self, a, n, x):
		start = 0
		summ = 0
		minn = 999999999
		for i in range(n):
			summ += a[i]
			if summ > x:
				minn = min(minn, i + 1)
				while summ > x and start <= i:
					summ -= a[start]
					if summ > x:
						start += 1
						minn = min(minn, i - start + 1)
					else:
						summ += a[start]
						break
		return minn


class Solution:

	def smallestSubWithSum(self, a, n, x):
		mini = float('inf')
		start = 0
		sum = 0
		for end in range(start, n):
			sum = sum + a[end]
			while sum > x and start <= end:
				mini = min(mini, end - start + 1)
				sum = sum - a[start]
				start = start + 1
		return mini


class Solution:

	def smallestSubWithSum(self, a, n, x):
		start = 0
		end = 0
		window_sum = 0
		min_len = 1000007
		while end < n and start <= end:
			window_sum += a[end]
			while window_sum > x:
				min_len = min(min_len, end - start + 1)
				window_sum -= a[start]
				start += 1
				if start > end:
					break
			end += 1
		if min_len == 1000007:
			return -1
		else:
			return min_len


class Solution:

	def smallestSubWithSum(self, a, n, x):
		ans = float('inf')
		left = 0
		curr_sum = 0
		for right in range(n):
			curr_sum += a[right]
			while curr_sum > x:
				ans = min(ans, right - left + 1)
				curr_sum -= a[left]
				left += 1
		return ans


class Solution:

	def smallestSubWithSum(self, a, n, x):
		cursum = 0
		min = n + 1
		s = 0
		e = 0
		while e < n:
			while cursum <= x and e < n:
				cursum += a[e]
				e += 1
			while cursum > x and s < n:
				if e - s < min:
					min = e - s
				cursum -= a[s]
				s += 1
		return min


class Solution:

	def smallestSubWithSum(self, a, n, x):
		sum = 0
		j = 0
		res = 9999
		for i in range(len(a)):
			sum += a[i]
			while sum > x:
				res = min(res, i - j)
				sum -= a[j]
				j += 1
		return res + 1


class Solution:

	def smallestSubWithSum(self, a, n, x):
		start = end = 0
		sum_ = 0
		ans = n
		while end < n:
			while end < n and sum_ <= x:
				sum_ += a[end]
				end += 1
			while start <= end and sum_ > x:
				sum_ -= a[start]
				start += 1
			ans = min(ans, end - start + 1)
		return ans


class Solution:

	def smallestSubWithSum(self, a, n, x):
		if n == 1 and a[0] > x:
			return n
		(start, end) = (0, 1)
		min_len = n
		arr_sum = a[0] + a[1]
		while start < n and end < n:
			if arr_sum > x:
				min_len = min(min_len, end - start + 1)
				arr_sum -= a[start]
				start += 1
			else:
				end += 1
				if end < n:
					arr_sum += a[end]
		return min_len


class Solution:

	def smallestSubWithSum(self, a, n, x):
		(l, total) = (0, 0)
		res = n + 1
		for r in range(len(a)):
			total += a[r]
			while total > x:
				res = min(r - l + 1, res)
				total -= a[l]
				l += 1
		return 0 if res == n + 1 else res


class Solution:

	def smallestSubWithSum(self, a, n, x):
		if n == 0:
			return 0
		if max(a) > x:
			return 1
		l = 0
		r = 1
		total = a[l]
		min_length = float('inf')
		while r < n:
			total = total + a[r]
			if total > x:
				if min_length == 0:
					min_length = len(a[l:r + 1])
				else:
					min_length = min(min_length, len(a[l:r + 1]))
				(l, r) = (l + 1, l + 2)
				total = a[l]
			else:
				r = r + 1
		return min_length


class Solution:

	def smallestSubWithSum(self, a, n, x):
		start = 0
		end = 0
		curr_sum = 0
		min_length = n + 1
		while end < n:
			while curr_sum <= x and end < n:
				curr_sum += a[end]
				end += 1
			while curr_sum > x and start < n:
				min_length = min(end - start, min_length)
				curr_sum -= a[start]
				start += 1
		return min_length


class Solution:

	def smallestSubWithSum(self, nums, n, x):
		length = float('inf')
		(i, j) = (0, 0)
		s = 0
		while j < n:
			s += nums[j]
			while s > x and i <= j:
				length = min(length, j - i + 1)
				s -= nums[i]
				i += 1
			j += 1
		if length == float('inf'):
			return 0
		return length


class Solution:

	def smallestSubWithSum(self, a, n, x):
		l = []
		(i, j) = (0, 0)
		s = 0
		diff = float('inf')
		while j < n:
			s += a[j]
			if s < x:
				j += 1
			elif s == x:
				s -= a[i]
				i += 1
				j += 1
			elif s > x:
				while s > x:
					diff = min(diff, j - i + 1)
					s -= a[i]
					i += 1
				j += 1
		return diff


class Solution:

	def smallestSubWithSum(self, a, n, x):
		s = 0
		c = 0
		ml = n + 1
		j = 0
		i = 0
		while j < n:
			while s <= x and j < n:
				s += a[j]
				j += 1
			while s > x and i < n:
				ml = min(ml, j - i)
				s -= a[i]
				i += 1
		return ml


class Solution:

	def smallestSubWithSum(self, a, n, x):
		if a[-1] > x:
			return 1
		res = n
		for j in range(n - 1):
			sm = 0
			sm += a[j]
			l = j + 1
			ans = 1
			while sm <= x and l < n:
				sm += a[l]
				l += 1
				ans += 1
			if sm > x:
				res = min(res, ans)
		return res


class Solution:

	def smallestSubWithSum(self, a, n, x):
		size = n + 1
		i = cur = j = 0
		while i < n:
			if cur + a[i] > x:
				size = min(size, i - j + 1)
				cur -= a[j]
				j += 1
			else:
				cur += a[i]
				i += 1
		return 0 if size == n + 1 else size


class Solution:

	def smallestSubWithSum(self, a, n, x):
		i = 0
		j = 0
		mx = 1000000000
		sum = 0
		c = 0
		while j < n:
			sum = sum + a[j]
			if sum <= x:
				j = j + 1
			elif sum > x:
				while sum > x:
					sum = sum - a[i]
					i = i + 1
				i = i - 1
				sum = sum + a[i]
				mx = min(mx, j - i + 1)
				j = j + 1
		return mx


class Solution:

	def smallestSubWithSum(self, a, n, x):
		rolling = [0] * n
		rolling[0] = a[0]
		if a[0] > x:
			return 1
		mlen = n
		for i in range(0, n):
			v = 0
			for j in range(i, n):
				v += a[j]
				if v > x:
					mlen = min(mlen, j - i + 1)
					break
		return mlen


class Solution:

	def smallestSubWithSum(self, a, n, x):
		i = 0
		j = 0
		s1 = 0
		ans = 10 ** 9
		while j <= n:
			if s1 <= x:
				if j == n:
					break
				s1 += a[j]
				j += 1
			else:
				ans = min(ans, j - i)
				s1 -= a[i]
				i += 1
		return ans


from itertools import combinations, permutations
from sys import maxsize

class Solution:

	def smallestSubWithSum(self, a, n, x):
		sum = 0
		count = 0
		start = 0
		min_length = maxsize + 1
		while count < n:
			sum = sum + a[count]
			if sum > x:
				for i in range(start, count + 1):
					sum = sum - a[i]
					if sum <= x:
						min_length = min(min_length, count - i + 1)
						count = i
						start = i + 1
						sum = 0
						break
			count += 1
		return min_length


class Solution:

	def smallestSubWithSum(self, arr, n, x):
		sum = 0
		j = 0
		count = n
		for i in range(n):
			sum += arr[i]
			while sum > x:
				sum -= arr[j]
				count = min(count, i - j + 1)
				j += 1
		return count


class Solution:

	def smallestSubWithSum(self, arr, n, x):
		i = 0
		j = 0
		temp_sum = 0
		mini = n
		while j < n or temp_sum > x:
			if temp_sum <= x:
				temp_sum += arr[j]
				j += 1
			else:
				mini = min(mini, j - i)
				temp_sum -= arr[i]
				i += 1
		return mini


class Solution:

	def smallestSubWithSum(self, a, n, x):
		total = 0
		end = 0
		start = 0
		ans = n + 1
		while end < n:
			while total <= x and end < n:
				total += a[end]
				end += 1
			while total > x and start < n:
				if end - start < ans:
					ans = end - start
				total -= a[start]
				start += 1
		return ans


class Solution:

	def smallestSubWithSum(self, a, n, x):
		l = 0
		su = 0
		count = 10000
		for i in range(n):
			su += a[i]
			while su > x:
				count = min(count, i - l + 1)
				su -= a[l]
				l += 1
		return count


class Solution:

	def smallestSubWithSum(self, a, n, x):
		ans = 1000000000.0
		sum = 0
		i = 0
		j = 0
		while j < n:
			while j < n:
				if sum > x:
					break
				sum += a[j]
				j += 1
			while i <= j:
				if sum - a[i] > x:
					sum -= a[i]
				else:
					ans = min(ans, j - i)
					sum -= a[i]
					i += 1
					break
				i += 1
		return ans


class Solution:

	def smallestSubWithSum(self, a, n, x):
		ans = len(a)
		(i, j) = (0, 0)
		sum1 = 0
		while j < len(a):
			sum1 += a[j]
			if sum1 <= x:
				j += 1
			elif sum1 > x:
				while sum1 > x:
					sum1 -= a[i]
					ans = min(ans, j - i + 1)
					i += 1
				j += 1
		return ans


class Solution:

	def smallestSubWithSum(self, a, n, x):
		i = 0
		j = 0
		ans = 10 ** 5
		Sum = 0
		while i < len(a):
			Sum += a[i]
			if Sum > x:
				if i - j + 1 < ans:
					ans = i - j + 1
				while Sum > x:
					Sum -= a[j]
					j += 1
					if Sum > x:
						if i - j + 1 < ans:
							ans = i - j + 1
			i += 1
		while Sum > x:
			Sum -= a[j]
			j += 1
			if Sum > x:
				if i - j + 1 < ans:
					ans = i - j + 1
		return ans


class Solution:

	def smallestSubWithSum(self, a, n, x):
		if max(a) > x:
			return 1
		low = 0
		high = 1
		s = a[low]
		ans = n
		if high < n:
			s += a[high]
		while low < n and high < n:
			if s > x:
				ans = min(ans, high - low + 1)
				s -= a[low]
				low += 1
			else:
				high += 1
				if high < n:
					s += a[high]
		return ans


class Solution:

	def smallestSubWithSum(self, a, n, x):
		summ = 0
		l = 0
		r = 0
		res = []
		while r < n:
			while r < n and summ <= x:
				summ = summ + a[r]
				r = r + 1
			while l < n and summ > x:
				summ = summ - a[l]
				res.append(r - l)
				l = l + 1
		return min(res)


class Solution:

	def smallestSubWithSum(self, arr, n, x):
		i = 0
		j = 0
		ans = n
		total = 0
		while j < n or total > x:
			if total > x:
				ans = min(ans, j - i)
				total -= arr[i]
				i += 1
			else:
				total += arr[j]
				j += 1
		return ans


class Solution:

	def smallestSubWithSum(self, a, n, x):
		i = 0
		s = 0
		res_val = n
		for j in range(n):
			s += a[j]
			while i <= j and s > x:
				if s > x:
					if j - i + 1 < res_val:
						res_val = j - i + 1
				s -= a[i]
				i += 1
		return res_val


class Solution:

	def smallestSubWithSum(self, a, n, x):
		i = 0
		j = 0
		ans = 0
		size = 100000
		while j < len(a):
			ans = ans + a[j]
			while ans > x:
				size = min(size, j - i + 1)
				ans = ans - a[i]
				i = i + 1
			else:
				j = j + 1
		if size == 100000:
			return 0
		return size


class Solution:

	def smallestSubWithSum(self, a, n, x):
		i = 0
		j = 0
		sum = 0
		len = n
		while j < n:
			if a[j] > x:
				return 1
			else:
				sum += a[j]
				if sum > x:
					len = min(len, j - i + 1)
					while sum - a[i] > x:
						sum -= a[i]
						i += 1
						len = min(len, j - i + 1)
			j += 1
		return len


class Solution:

	def smallestSubWithSum(self, arr, n, x):
		min_length = 2 ** 64
		start = 0
		end = 0
		current_sum = 0
		while end < len(arr):
			current_sum = current_sum + arr[end]
			end += 1
			while start < end and current_sum > x:
				current_sum = current_sum - arr[start]
				start += 1
				min_length = min(min_length, end - start + 1)
		return min_length


class Solution:

	def smallestSubWithSum(self, arr, n, x):
		cs = 0
		ml = n + 1
		st = en = 0
		while en < n:
			while cs <= x and en < n:
				cs += arr[en]
				en += 1
			while cs > x and st < n:
				if en - st < ml:
					ml = en - st
				cs -= arr[st]
				st += 1
		return ml


class Solution:

	def smallestSubWithSum(self, a, n, x):
		s = 0
		e = 0
		c_s = 0
		min_len = n + 1
		while e < n:
			while c_s <= x and e < n:
				c_s += a[e]
				e += 1
			while c_s > x and s < n:
				if e - s < min_len:
					min_len = e - s
				c_s -= a[s]
				s += 1
		return min_len


class Solution:

	def smallestSubWithSum(self, a, n, x):
		curr_sum = 0
		(i, j) = (0, 0)
		l = 99999999
		while j < n:
			curr_sum += a[j]
			while i < n and curr_sum > x:
				l = min(l, j - i + 1)
				curr_sum -= a[i]
				i += 1
			j += 1
		return l


class Solution:

	def smallestSubWithSum(self, a, n, x):
		i = 0
		j = 0
		s = 0
		min1 = 10 ** 5
		while i < n:
			while i < n and s <= x:
				s += a[i]
				i += 1
			while j <= i and s > x:
				s -= a[j]
				j += 1
			min1 = min(min1, i - j + 1)
		return min1


class Solution:

	def smallestSubWithSum(self, a, n, x):
		min_l = n
		for i in range(n):
			s = 0
			for j in range(i, n):
				s += a[j]
				if s > x:
					min_l = min(min_l, j - i + 1)
					break
		return min_l


import sys

class Solution:

	def smallestSubWithSum(self, arr, n, x):
		i = 0
		j = 0
		mn = n
		sm = 0
		while j < n:
			sm += arr[j]
			if sm < x:
				j += 1
			elif sm == x:
				j += 1
			elif sm > x:
				while sm > x:
					mn = min(mn, j - i + 1)
					sm -= arr[i]
					i += 1
				j += 1
		return mn


class Solution:

	def smallestSubWithSum(self, a, n, x):
		res = n + 1
		start = 0
		end = 0
		tsum = 0
		while end < n:
			while tsum <= x and end < n:
				tsum += a[end]
				end += 1
			while tsum > x and start < n:
				temp = end - start
				if temp < res:
					res = temp
				tsum -= a[start]
				start += 1
		return res


class Solution:

	def smallestSubWithSum(self, a, n, x):
		(start, end, maxLen, sum) = (0, 0, n, 0)
		while end < n:
			while sum <= x and end < n:
				sum += a[end]
				end += 1
			while sum > x:
				maxLen = min(maxLen, end - start)
				sum -= a[start]
				start += 1
		return maxLen


class Solution:

	def smallestSubWithSum(self, arr, n, x):
		l = 0
		r = 0
		s = 0
		m = n + 1
		while r < n:
			while s <= x and r < n:
				s += arr[r]
				r += 1
			while s > x and l < n:
				m = min(m, r - l)
				s -= arr[l]
				l += 1
		return m


class Solution:

	def smallestSubWithSum(self, a, n, x):
		(start, end) = (0, 1)
		result = n * 10
		sumres = a[start]
		if sumres > x:
			return 1
		if end < n:
			sumres += a[end]
		while start <= end and end < n:
			if sumres > x:
				result = min(result, end - start + 1)
				sumres -= a[start]
				start += 1
			else:
				end += 1
				if end < n:
					sumres += a[end]
		return result


class Solution:

	def smallestSubWithSum(self, a, n, x):
		ml = 999999
		s = 0
		j = 0
		for i in range(n):
			s += a[i]
			while s > x and j <= i:
				ml = min(ml, i - j + 1)
				s -= a[j]
				j += 1
				if s <= x:
					break
		return ml


class Solution:

	def smallestSubWithSum(self, a, n, x):
		sum = 0
		len = n + 1
		s = 0
		e = 0
		while e < n:
			while e < n and sum <= x:
				sum += a[e]
				e += 1
			while sum > x and s < n:
				if e - s < len:
					len = e - s
				sum -= a[s]
				s += 1
		return len


class Solution:

	def smallestSubWithSum(self, a, n, x):
		ind = 0
		summ = 0
		count = n + 1
		for i in range(n):
			summ += a[i]
			if a[i] > x:
				return 1
			if summ > x:
				if i - ind + 1 < count:
					count = i - ind + 1
				while summ > x:
					if i - ind + 1 < count:
						count = i - ind + 1
					summ -= a[ind]
					ind += 1
		return count


class Solution:

	def smallestSubWithSum(self, a, n, x):
		s = 0
		e = 0
		csum = 0
		res = float('inf')
		while e < n:
			csum += a[e]
			e += 1
			while s < e and csum > x:
				csum = csum - a[s]
				s = s + 1
				res = min(res, e - s + 1)
		return res


class Solution:

	def smallestSubWithSum(self, a, n, x):
		na = []
		sum = 0
		j = 0
		l = 0
		for i in range(n):
			sum = sum + a[i]
			l = l + 1
			while sum > x and j <= i:
				na.append(l)
				sum = sum - a[j]
				j = j + 1
				l = l - 1
		return min(na)


class Solution:

	def smallestSubWithSum(self, a, n, x):
		(start, end) = (0, 0)
		result = float('inf')
		total = 0
		while end <= len(a) - 1:
			val = a[end]
			total += val
			if total > x:
				result = min(result, end - start + 1)
			while total > x and start <= end:
				val = a[start]
				start += 1
				total -= val
				if total > x:
					result = min(result, end - start + 1)
			end += 1
		return result