How to find the largest subarray with sum = k in the given array efficiently ?

Question

N is the length of array .

1<=N<=1000000

-100000<=A[i]<=100000

Explaining algorithm is mandatory. Only giving code and no explanation is not allowed. Also add your name at the bottom of answer so you get the due credits. Direct libraries in python are not allowed to be used as they skip the lagorithm parts sometimes.

 

Example Array : 4 -8 7 8 -100 15

k=15

Output : {7,8} is the largesr subarray with sum =15

Answer 1

//Time = O(n)
//space = O(n)
//we will store the prefix sum as key, and the index as value in a map(index denotes the prefix sum till that point
//we will iterate the array,calculate the prefix sum till that point, if (prefixsum-k) is present in the map, then find the index of prefixsum-k, subtract the current counter and find the maximim length

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,sum=0,k,x,j;
    cin>>n>>k;
    vector<int> a(n);
    map<int,int> mp;
    
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        
    }
    int mx=INT_MIN;
    mp[0]=0;
    for(int i=0;i<n;i++)
    {
    
        sum+=a[i];
        if(mp.find(sum-k)!=mp.end())
        {
            j=mp[sum-k];
            mx=max(mx,i-j);
        }
        mp[sum]=i+1;
    }
    if(mx<n)
        cout<<++mx;
    else
        cout<<" no subarray where sum= k";
}

Answer 2

l=[1,5,6,7,8]   #l=list(map(int,input().split())) or l=[int(x) for x in input().split()]
k=11            #k=input()
le,c=0,0        #le for calculating length of the array,
for i in l:
    le+=1
for i in range(len(l)):    #i as starting index and j as ending index
    for j in range(i+1,len(l)+1):
        s=0
        for i in range(i,j):
            #print(i,j)
            s+=l[i]
            #print('s =',s)
        if s==k:
            c+=1
print(c)

 

Time Complexity : O(N^2) 

Comments

Your approach is not efficient . It uses 2 nested-for loops , hence the time complexity will be O(n*n) .