TLE in Hashing O(N)

Ques- Here I need to find the sub-array with given sum but I am constantly getting TLE. According to me my solution is in O(n).
Here is the question link
https://practice.geeksforgeeks.org/problems/subarray-with-given-sum/0
Here is my attempt:
https://ide.geeksforgeeks.org/m1QLsFBjnd
Afaik Unordered map find() also works in O(1). So what’s causing TLE error?
Thanks in advance!

One reason of TLE might be that the worst case complexity of unordered map is O(n). :slight_smile:

1 Like

@aditya_akash o(n) or o(n^2)??

O(n). updated :slight_smile:

So how to solve this by STL? @aditya_akash

I don’t think any STL is required to solve this question. You can use the concept of two pointers to calculate the sum of possible sub arrays.

You may refer this code.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define boost ios_base::sync_with_stdio(false);cin.tie(NULL);
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define M 1000000007
#define inf 1e18
#define all(a) (a).begin(),(a).end()

int main()
{

    //boost
    //double const pi = 3.14159265358979;
    int t,k,i,j;
    //ll M =1000000007;
    int n;
    cin>>t;
    while(t--)
    {
        int sum;
        cin>>n>>sum;
        int a[n];
        for(i=0;i<n;i++)cin>>a[i];
        i=0;
        j=0;
        ll cur=0;
        pair<int,int> ans = {-1,-1};

        for(i=0;i<n;i++) {
            if(i>j){
                j=i;
                cur=0;
            }
            while(j<n && cur + a[j]<=sum) {
                cur += a[j];
                if(cur != sum)
                    j++;
                //cerr<<cur<<" "<<i<<" "<<j<<"\n";
            }
            if(cur == sum ){
                ans = {i,j};
                break;
            }
            cur -= a[i];
        }
        if(ans.fi==-1) cout<<"-1\n";
        else {
            cout<<ans.fi +1<<" "<<ans.se+1<<"\n";
        }
    }
	return 0;
}

1 Like