0
  1. Iam getting error as TLE due to complexity O(n logn) whereas given Qs needs to be solved in O(n).
  2. Need to find alternative of m.find() method as it is taking O(logn) complexity and total complexity becomes O(nlog n).
    vector<int> subarraySum(int a[], int n, long long s)
    {
       vector<int> result;
       map<int,int>m;
       map<int,int>::iterator it;
       int b[n];
       b[0]=a[0];
       for(int i=1;i<n;i++){
           b[i]=b[i-1]+a[i];
        }
          
        for(int i=0;i<n;i++){
            m.insert({ b[i],i });
        }
        for(it=m.begin();it!=m.end();it++){
          if((it->first-s)==0){
            result.push_back(1);
            result.push_back((it->second)+1);
            break;
            }
            if(m.find(it->first-s)!=m.end()){
               result.push_back(m[it->first-s]+2);
               result.push_back((it->second)+1);
                break;
             }
        }
           if(result.empty())
            result.push_back(-1);
            return result;
    }
ujjwal kumar
  • 1
  • 1
    Careful with `int b[n];`. That's a Variable Length Array. [Standard C++ doesn't support them for a bunch of good reasons](https://stackoverflow.com/q/1887097/4581301), my personal favourite being they're just asking for stack overflows unless you restrict the maximum size. – user4581301 Jul 05 '22 at 19:03
  • `int b[n];` -- You are already using `std::vector`, but for some reason, you refused to use it here. This should be `std::vector b(n);`. – PaulMcKenzie Jul 05 '22 at 19:46
  • I understood about vector and array but my question is of time complexity. Please answer that if possible. – ujjwal kumar Jul 05 '22 at 20:03
  • Take a look at `std::unordered_map`. Unless you hit a deviant data pattern access is typically O(1). If the values in `b` are bounded nicely, you can allocate a big honking array and use `b` as indexes. That'll give you O(1) for sure. – user4581301 Jul 05 '22 at 20:15
  • 1
    Side note: you'll find question like this about an online judge challenges tend to get ignored or closed. If the pool of folk answering questions here were interested in these sorts of questions, they would be answering questions at the judging sites rather than answering questions here. – user4581301 Jul 05 '22 at 20:18
  • @ujjwalkumar *I understood about vector and array but my question is of time complexity.* -- How do you know that the usage of that fake array wouldn't have an effect on the timing? Second, the comment section is for comments, not for answers -- you posted code that had these issues, and comments were made. The answer section is for answers. I know you are new, but effectively telling contributors to keep quiet and answer your question isn't the way to make a good first impression. – PaulMcKenzie Jul 05 '22 at 20:38
  • @PaulMcKenzie I got the point. Apologise for that comment.Yes u r right, Im new here. – ujjwal kumar Jul 05 '22 at 21:03
  • Please clarify your specific problem or provide additional details to highlight exactly what you need. As it's currently written, it's hard to tell exactly what you're asking. – Community Jul 17 '22 at 09:01

1 Answers1

0

You are supposed to learn the sliding window algorithm: https://en.wikipedia.org/wiki/Streaming_algorithm

Goswin von Brederlow
  • 11,875
  • 2
  • 24
  • 42