Sub Array Sum Efficient Code

In this class, We discuss Sub Array Sum Efficient Code.

For Complete YouTube Video: Click Here

The reader should have prior knowledge of basic programming. Click Here.

Given an array of N positive integers and a sum value.

Example:

1, 8, 5, 2, 3, 4,

Sum = 7

Find a continuous sub-array whose sum of elements in the sub-array = given sum.

If there are multiple sub-arrays, we need to return the index of the first sub-array from the left.

Time complexity = O(n)

Space complexity = O(1)

Input: 1, 8, 5, 2, 3, 4

Output: [3,4]

We provide the intuition on how to write the code in the video.

The video link is above.

Code:

def subArraySum(arr, n, s):

    lis=[]

    start=0

    end=0

    summ=arr[0]

    for i in range(1,n):

        if summ > s:

            summ=summ-arr[start]

            start = start+1

            if summ==s:

                break

            else:

                summ=summ+arr[i]

                end=i

        elif summ < s:

            summ=summ+arr[i]

            end = i

            if summ==s:

                break

            if summ > s:

                while(summ>s):

                    summ=summ-arr[start]

                    start=start+1

                if summ==s:

                    break

        else:

            break

    if summ==s:

        lis.append(start+1)

        lis.append(end+1)

    else:

        lis.append(-1)

    return lis

n = int(input(“enter number of elements”))

s = int(input(“eneter sum value”))

arr = []

print(“enter positive n elements”)

for i in range(n):

    x =int(input())

    arr.append(x)

lis=subArraySum(arr,n,s)

print(lis)