Given an unsorted array A of size N that contains only positive integers, find a continuous sub-array that adds to a given number S and return the left and right index(1-based indexing) of that subarray.
In case of multiple subarrays, return the subarray indexes which come first on moving from left to right.
Note:- You have to return an ArrayList consisting of two elements left and right. In case no such subarray exists return an array consisting of element -1.
Example 1:
Input:
N = 5, S = 12
A[] = {1,2,3,7,5}
Output: 2 4
Explanation: The sum of elements 
from 2nd position to 4th position 
is 12.
 
Example 2:
Input:
N = 10, S = 15
A[] = {1,2,3,4,5,6,7,8,9,10}
Output: 1 5
Explanation: The sum of elements 
from 1st position to 5th position
is 15.
 
Your Task:
You don't need to read input or print anything. The task is to complete the function subarraySum() which takes arr, N, and S as input parameters and returns an ArrayList containing the starting and ending positions of the first such occurring subarray from the left where sum equals to S. The two indexes in the array should be according to 1-based indexing. If no such subarray is found, return an array consisting of only one element that is -1.
 
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
 
Constraints:
1 <= N <= 10^{5}
1 <= A_{i} <= 10^{9}
0<= S <= 10^{14}

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Amortized analysis

Range queries

Complete search

Starter code: #User function Template for python3



#Function to find a continuous sub-array which adds up to a given number.

class Solution:

    def subArraySum(self,arr, n, s): 

       #Write your code here

Solutions:
class Solution:

	def subArraySum(self, arr, n, s):
		(i, j) = (0, 0)
		summ = 0
		while j < n:
			summ += arr[j]
			while summ > s and i < j:
				summ -= arr[i]
				i += 1
				if summ == s:
					return [i + 1, j + 1]
			if summ == s:
				return [i + 1, j + 1]
			j += 1
		return [-1]


class Solution:

	def subArraySum(self, numbers: list, n: int, s: int) -> tuple:
		if n < 1 or n > 10 ** 5 or s < 0 or (s > 10 ** 14) or (s == 0):
			return [-1]
		(c, start, end) = (0, 0, 0)
		while end < n:
			c += numbers[end]
			while c > s:
				c -= numbers[start]
				start += 1
			if c == s:
				return [start + 1, end + 1]
			end += 1
		return [-1]


class Solution:

	def subArraySum(self, arr, n, s):
		st = 0
		en = 0
		cur_sum = 0
		if s == 0 and arr.count(0) < 1:
			return [-1]
		while en < n:
			cur_sum += arr[en]
			while cur_sum > s:
				cur_sum -= arr[st]
				st += 1
			if cur_sum == s:
				return [st + 1, en + 1]
			en += 1
		return [-1]


class Solution:

	def subArraySum(self, arr, n, s):
		start = 0
		end = 0
		curr_sum = 0
		if s == 0:
			return [-1]
		while end < n:
			curr_sum += arr[end]
			while curr_sum > s and start <= end:
				curr_sum -= arr[start]
				start += 1
			if curr_sum == s:
				return [start + 1, end + 1]
			end += 1
		return [-1]


class Solution:

	def subArraySum(self, arr, n, s):
		currentsum = arr[0]
		start = 0
		i = 1
		while i <= n:
			while currentsum > s and start < i - 1:
				currentsum = currentsum - arr[start]
				start = start + 1
			if currentsum == s:
				return [start + 1, i]
			if i < n:
				currentsum = currentsum + arr[i]
			i = i + 1
		return [-1]


class Solution:

	def subArraySum(self, arr, n, s):
		curr = 0
		l = 0
		if s == 0:
			return [-1]
		for r in range(n):
			curr += arr[r]
			while curr > s:
				curr -= arr[l]
				l += 1
			if curr == s:
				return (l + 1, r + 1)
		return [-1]


class Solution:

	def subArraySum(self, arr, n, s):
		start = 0
		end = 0
		current_sum = 0
		if s == 0:
			return [-1]
		while end < n:
			current_sum += arr[end]
			while current_sum > s:
				current_sum -= arr[start]
				start += 1
			if current_sum == s:
				return [start + 1, end + 1]
			end += 1
		return [-1]


class Solution:

	def subArraySum(self, arr, n, s):
		left = 0
		right = 0
		sum = 0
		while right < n:
			sum += arr[right]
			while sum > s:
				sum -= arr[left]
				left += 1
			if sum == s and right >= left:
				return [left + 1, right + 1]
			right += 1
		return [-1]


class Solution:

	def subArraySum(self, arr, n, sum_):
		A = []
		curr_sum = arr[0]
		start = 0
		i = 1
		while i <= n:
			while curr_sum > sum_ and start < i - 1:
				curr_sum = curr_sum - arr[start]
				start += 1
			if curr_sum == sum_:
				A.append(start + 1)
				A.append(i)
				return A
			if i < n:
				curr_sum = curr_sum + arr[i]
			i += 1
		A.append(-1)
		return A


from sys import maxsize

class Solution:

	def subArraySum(self, arr, n, sum):
		currentsum = arr[0]
		begin = 0
		i = 1
		while i <= n:
			while currentsum > sum and begin < i - 1:
				currentsum = currentsum - arr[begin]
				begin = begin + 1
			if currentsum == sum:
				return [begin + 1, i]
			if i < n:
				currentsum = currentsum + arr[i]
			i = i + 1
		return [-1]


class Solution:

	def subArraySum(self, arr, n, s):
		if s == 0:
			return [-1]
		(i, j) = (0, 0)
		current_sum = 0
		while j < n:
			current_sum += arr[j]
			while current_sum > s:
				current_sum -= arr[i]
				i += 1
			if current_sum == s:
				return [i + 1, j + 1]
			j += 1
		return [-1]


class Solution:

	def subArraySum(self, arr, n, s):
		(l, r) = (0, 0)
		x = arr[0]
		if s == 0:
			return [-1]
		while l < n:
			while s > x and r < n - 1:
				r += 1
				x += arr[r]
			if s == x:
				return [l + 1, r + 1]
			elif s < x:
				x -= arr[l]
				l += 1
				while s <= x:
					x -= arr[r]
					r -= 1
			else:
				break
		return [-1]


class Solution:

	def subArraySum(self, arr, n, s):
		curr_sum = 0
		left = 0
		subarray = []
		for right in range(n):
			curr_sum += arr[right]
			while curr_sum > s:
				curr_sum -= arr[left]
				left += 1
			if curr_sum == s:
				subarray = [left + 1, right + 1]
				break
		if not subarray:
			subarray = [-1]
		if s == 0:
			subarray = [-1]
		return subarray


class Solution:

	def subArraySum(self, arr, n, s):
		start = 0
		current_sum = 0
		if s == 0:
			return [-1]
		else:
			for end in range(n):
				current_sum += arr[end]
				while current_sum > s:
					current_sum -= arr[start]
					start += 1
				if current_sum == s:
					return [start + 1, end + 1]
			return [-1]


class Solution:

	def subArraySum(self, arr, n, s):
		start = 0
		sum = 0
		for (end, num) in enumerate(arr):
			sum += num
			while sum > s and start < end:
				sum -= arr[start]
				start += 1
			if sum == s:
				return [start + 1, end + 1]
		return [-1]


class Solution:

	def subArraySum(self, arr, n, s):
		pehl = 0
		sum = 0
		aslisum = 0
		for i in arr:
			aslisum += i
		aakh = 1
		sum += arr[0]
		if sum > aslisum:
			return [-1]
		while True:
			if sum == s:
				if pehl >= aakh:
					return [-1]
				else:
					return [pehl + 1, aakh]
			if pehl > aakh or aakh > n:
				return [-1]
			elif sum > s:
				sum -= arr[pehl]
				pehl += 1
			else:
				if aakh >= n:
					return [-1]
				sum += arr[aakh]
				aakh += 1


class Solution:

	def subArraySum(self, arr, n, s):
		dict = {}
		cur_sum = 0
		for i in range(n):
			cur_sum = cur_sum + arr[i]
			if cur_sum == s:
				return [1, i + 1]
				break
			if cur_sum - s in dict:
				left = dict[cur_sum - s] + 1
				right = i + 1
				return [left, right]
			dict[cur_sum] = i + 1
		return [-1]


class Solution:

	def subArraySum(self, arr, n, s):
		dict1 = {}
		curr_sum = 0
		for i in range(n):
			curr_sum += arr[i]
			if curr_sum == s:
				return [1, i + 1]
			if curr_sum - s in dict1:
				return [dict1[curr_sum - s] + 2, i + 1]
			dict1[curr_sum] = i
		return [-1]


class Solution:

	def subArraySum(self, arr, n, s):
		sum_dict = {0: 0}
		curr_sum = 0
		for i in range(n):
			curr_sum = curr_sum + arr[i]
			if curr_sum - s in sum_dict:
				left = sum_dict[curr_sum - s] + 1
				right = i + 1
				return [left, right]
			sum_dict[curr_sum] = i + 1
		return [-1]


class Solution:

	def subArraySum(self, arr, n, s):
		sum = 0
		x = 0
		r = 0
		while r < len(arr):
			sum += arr[r]
			while sum > s and s != 0:
				sum -= arr[x]
				x += 1
			if sum == s:
				return [x + 1, r + 1]
			r += 1
		return [-1]


class Solution:

	def subArraySum(self, arr, n, s):
		subsum = 0
		begin_index = 0
		pos = []
		for i in range(0, n):
			subsum = subsum + arr[i]
			while subsum > s and begin_index < i:
				subsum = subsum - arr[begin_index]
				begin_index = begin_index + 1
			if subsum == s:
				pos.append(begin_index + 1)
				pos.append(i + 1)
				return pos
		pos.append(-1)
		return pos


class Solution:

	def subArraySum(self, arr, n, s):
		(current_index, cont_sum) = (0, 0)
		all_sum = sum(arr)
		start_index = 1
		cont_sum += arr[0]
		if cont_sum > all_sum:
			return [-1]
		while True:
			if cont_sum == s:
				if current_index >= start_index:
					return [-1]
				else:
					return [current_index + 1, start_index]
			if current_index > start_index or start_index > n:
				return [-1]
			elif cont_sum > s:
				cont_sum -= arr[current_index]
				current_index += 1
			else:
				if start_index >= n:
					return [-1]
				cont_sum += arr[start_index]
				start_index += 1


class Solution:

	def subArraySum(self, arr, n, s):
		(current_index, cont_sum, all_sum) = (0, 0, 0)
		for i in arr:
			all_sum += i
		start_index = 1
		cont_sum += arr[0]
		if cont_sum > all_sum:
			return [-1]
		while True:
			if cont_sum == s:
				if current_index >= start_index:
					return [-1]
				else:
					return [current_index + 1, start_index]
			if current_index > start_index or start_index > n:
				return [-1]
			elif cont_sum > s:
				cont_sum -= arr[current_index]
				current_index += 1
			else:
				if start_index >= n:
					return [-1]
				cont_sum += arr[start_index]
				start_index += 1


class Solution:

	def subArraySum(self, arr, n, s):
		l = 0
		cur_sum = 0
		if s == 0:
			return [-1]
		for i in range(n):
			cur_sum += arr[i]
			if cur_sum == s:
				return [l + 1, i + 1]
			elif cur_sum > s:
				while cur_sum > s:
					cur_sum -= arr[l]
					l += 1
				if cur_sum == s:
					return [l + 1, i + 1]
		return [-1]


class Solution:

	def subArraySum(self, arr, n, s):
		currentSum = 0
		startIndex = 0
		endIndex = -1
		for i in range(len(arr)):
			currentSum += arr[i]
			while currentSum > s:
				currentSum -= arr[startIndex]
				startIndex += 1
				if currentSum < 0:
					break
			if currentSum == s:
				endIndex = i
				currentSum = s
				break
		if endIndex == -1 or startIndex > endIndex:
			return [-1]
		return [startIndex + 1, endIndex + 1]


class Solution:

	def subArraySum(self, arr, n, s):
		d = {}
		cs = 0
		for i in range(n):
			cs = cs + arr[i]
			d[cs] = i
			if cs == s and i + 1 >= 1:
				return [1, i + 1]
			if cs - s in d:
				if d[cs - s] + 2 <= i + 1:
					return [d[cs - s] + 2, i + 1]
		return [-1]


class Solution:

	def subArraySum(self, arr, n, s):
		current_sum = 0
		dp = {}
		for i in range(len(arr)):
			current_sum += arr[i]
			if current_sum == s:
				return [1, i + 1]
			if current_sum - s in dp:
				return [dp[current_sum - s] + 2, i + 1]
			dp[current_sum] = i
		return [-1]


class Solution:

	def subArraySum(self, arr, n, s):
		wst = 0
		wend = 0
		s1 = 0
		l = []
		if s == 0:
			l.append(-1)
			return l
		while wend < n:
			if s1 < s:
				s1 += arr[wend]
				wend += 1
			while s1 > s:
				s1 -= arr[wst]
				wst += 1
			if s1 == s:
				l.append(wst + 1)
				l.append(wend)
				return l
		l.append(-1)
		return l


class Solution:

	def subArraySum(self, arr, n, s):
		currsum = {}
		currsum[0] = -1
		sums = 0
		for i in range(n):
			sums += arr[i]
			if sums - s in currsum:
				return (currsum[sums - s] + 2, i + 1)
			else:
				currsum[sums] = i
		return [-1]


class Solution:

	def subArraySum(self, arr, n, s):
		l = 0
		r = 1
		su = arr[l]
		f = True
		if s == 0:
			f = False
		while l <= r and f:
			if su < s:
				if r > len(arr) - 1:
					break
				su += arr[r]
				r += 1
			elif su > s:
				su -= arr[l]
				l += 1
			elif su == s:
				return [l + 1, r]
		return [-1]


class Solution:

	def subArraySum(self, arr, n, s):
		if s == 0:
			return [-1]
		else:
			start = 0
			end = 0
			sum = arr[0]
			while end < n:
				if sum == s:
					return [start + 1, end + 1]
				elif sum < s:
					end += 1
					if end == n:
						break
					sum += arr[end]
				else:
					sum -= arr[start]
					start += 1
			return [-1]


class Solution:

	def subArraySum(self, arr, n, s):
		(currSum, chk) = (0, {0: 0})
		for (i, x) in enumerate(arr):
			currSum += x
			if currSum - s in chk:
				return [chk[currSum - s] + 1, i + 1]
			chk[currSum] = i + 1
		return [-1]


class Solution:

	def subArraySum(self, arr, n, s):
		r = []
		left = 0
		right = 0
		sum = arr[0]
		while left < n and right < n:
			while sum > s:
				sum = sum - arr[left]
				left += 1
			if sum == s:
				if left <= right:
					r.append(left + 1)
					r.append(right + 1)
					left = right + 1
					right = right + 1
				break
				if right < n:
					sum = arr[right]
				continue
			right = right + 1
			if right < n:
				sum = sum + arr[right]
		n1 = len(r)
		if n1 == 0:
			r.append(-1)
		return r


class Solution:

	def subArraySum(self, arr, n, s):
		if s == 0:
			return [-1]
		summ = 0
		idx = 0
		for i in range(n):
			summ += arr[i]
			while summ > s:
				summ -= arr[idx]
				idx += 1
			if summ == s:
				return [idx + 1, i + 1]
		return [-1]


class Solution:

	def subArraySum(self, arr, n, s):
		indx1 = 0
		indx2 = 0
		sum = 0
		if arr[indx1] == s:
			return [1, 1]
		else:
			while indx2 <= n - 1 and s:
				if sum + arr[indx2] <= s:
					sum += arr[indx2]
					indx2 += 1
				else:
					sum -= arr[indx1]
					indx1 += 1
				if sum == s:
					return [indx1 + 1, indx2]
		return [-1]


class Solution:

	def subArraySum(self, arr, n, k):
		cur_sum = arr[0]
		(i, j) = (0, 1)
		while j <= n:
			while cur_sum > k and i < j - 1:
				cur_sum -= arr[i]
				i += 1
			if cur_sum == k:
				return [i + 1, j]
			if j < n:
				cur_sum += arr[j]
			j += 1
		return [-1]


class Solution:

	def subArraySum(self, arr, n, s):
		(l, r) = (0, 0)
		d = 0
		while r < n:
			d += arr[r]
			while d > s and l < r:
				d -= arr[l]
				l += 1
				if d == s:
					return [l + 1, r + 1]
			if d == s:
				return [l + 1, r + 1]
			r += 1
		return [-1]


class Solution:

	def subArraySum(self, arr, n, s):
		if s == 0:
			return [-1]
		Sum = 0
		j = 0
		for i in range(n):
			Sum += arr[i]
			if Sum == s:
				return [j + 1, i + 1]
			if Sum > s:
				while Sum > s:
					Sum -= arr[j]
					j += 1
					if Sum == s:
						return [j + 1, i + 1]
		return [-1]


class Solution:

	def subArraySum(self, arr, n, s):
		left = right = 0
		cur = arr[0]
		if s == 0:
			return [-1]
		while right < n and left < n:
			if cur < s:
				right += 1
				if right < n:
					cur += arr[right]
			elif cur == s:
				return [left + 1, right + 1]
			else:
				cur -= arr[left]
				left += 1
		return [-1]


class Solution:

	def subArraySum(self, arr, n, s):
		(i, j) = (0, -1)
		sm = 0
		for k in range(n):
			sm += arr[k]
			j += 1
			while sm > s:
				sm -= arr[i]
				i += 1
			if sm == s and i <= j:
				return [i + 1, j + 1]
		return [-1]


class Solution:

	def subArraySum(self, arr, n, s):
		S = 0
		j = 0
		for i in range(0, n):
			S = S + arr[i]
			if S == s:
				return (j + 1, i + 1)
			elif S > s:
				while S > s:
					S = S - arr[j]
					j = j + 1
					if S == s and j != i + 1:
						return (j + 1, i + 1)
		return [-1]


class Solution:

	def subArraySum(self, arr, n, s):
		l = 0
		r = -1
		sum = 0
		for i in range(n):
			sum += arr[i]
			r += 1
			if sum == s:
				return [l + 1, r + 1]
			while sum > s and l < r:
				sum -= arr[l]
				l += 1
				if sum == s:
					return [l + 1, r + 1]
		return [-1]


class Solution:

	def subArraySum(self, arr, n, s):
		start = 0
		cursum = arr[start]
		if cursum == s:
			return [start + 1, start + 1]
		for j in range(start + 1, n):
			cursum = cursum + arr[j]
			while cursum > s and start < j:
				cursum = cursum - arr[start]
				start += 1
			if cursum == s:
				return [start + 1, j + 1]
		return [-1]


class Solution:

	def subArraySum(self, arr, n, s):
		if s == 0:
			return [-1]
		S = 0
		st = 0
		for i in range(n):
			S += arr[i]
			while S > s:
				S -= arr[st]
				st += 1
			if S == s:
				return [st + 1, i + 1]
		return [-1]


class Solution:

	def subArraySum(self, arr, n, sum_):
		currentSum = arr[0]
		start = 0
		i = 1
		while i <= n:
			while currentSum > sum_ and start < i - 1:
				currentSum = currentSum - arr[start]
				start += 1
			if currentSum == sum_:
				return (start + 1, i)
			if i < n:
				currentSum = currentSum + arr[i]
			i += 1
		return [-1]


class Solution:

	def subArraySum(self, arr, n, s):
		a = 0
		l = []
		p = [-1]
		c = 0
		if s == 0:
			return p
		for i in range(0, n):
			a += arr[i]
			while a > s:
				a -= arr[c]
				c += 1
			if a == s:
				l.append(c + 1)
				l.append(i + 1)
				return l
		return p


class Solution:

	def subArraySum(self, arr, n, s):
		start = 0
		end = 0
		sum = arr[end]
		flag = 0
		result = []
		if s == 0:
			result.append(-1)
			return result
		while start < n and end < n:
			if sum == s:
				flag = 1
				result.append(start + 1)
				result.append(end + 1)
				break
			elif sum < s and end < n - 1:
				end = end + 1
				sum = sum + arr[end]
			elif sum > s:
				sum = sum - arr[start]
				start = start + 1
			else:
				break
		if flag == 0:
			result.append(-1)
		return result


class Solution:

	def subArraySum(self, arr, n, s):
		curr_sum = 0
		start = 0
		for i in range(0, n):
			if curr_sum < s:
				curr_sum = curr_sum + arr[i]
			if curr_sum > s:
				while curr_sum > s:
					curr_sum = curr_sum - arr[start]
					start = start + 1
			if curr_sum == s:
				if [start, i] == [0, 0] and s != arr[0]:
					return [-1]
				return [start + 1, i + 1]
		return [-1]


class Solution:

	def subArraySum(self, arr, n, s):
		i = 0
		j = 0
		sum1 = 0
		while i <= j and i < n and (j <= n):
			if sum1 < s and j < n:
				sum1 += arr[j]
				j += 1
			elif sum1 == s and j != 0:
				return (i + 1, j)
			else:
				sum1 -= arr[i]
				i += 1
		return [-1]


class Solution:

	def subArraySum(self, array, n, s):
		sum = array[0]
		start = 0
		i = 1
		flag = False
		while i <= n:
			while sum > s and start < i - 1:
				sum = sum - array[start]
				start += 1
			if sum == s:
				flag = True
				break
			if i < n:
				sum = sum + array[i]
			i += 1
		return [start + 1, i] if flag else [-1]


class Solution:

	def subArraySum(self, arr, n, s):
		i = 0
		j = 0
		curr = 0
		while j < len(arr):
			curr += arr[j]
			while curr > s:
				curr -= arr[i]
				i += 1
			if curr == s and i <= j:
				return [i + 1, j + 1]
			j += 1
		return [-1]