How to decrease time complexity

[Pen72]

Given sequence A=(a1,a2...an)
find Kth Smallest Element in iteration A[1,k],A[a,k+1]...A[1,n]

For the Input Format, the first line is n and k,
the second line is sequence A

Sample Input 0

5 2
9 8 1 2 0

Sample Output 0

9 8 2 1

Explanation:
A[1,2]=(9,8), the 2nd smallest element is 9
A[1,3]=(9,8,1), the 2nd smallest element is 8
A[1,4]=(9,8,1,2), the 2nd smallest element is 2
A[1,5]=(9,8,1,2,0), the 2nd smallest element is 1

Below is my attempt, can pass test case 0 but appears to be time out after test case 1, how can I lower time complexity

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include<climits>
using namespace std;



int main() {
int n,k,l,q=0;
cin >> n >> k;
vector<int>arr(n);
vector<int> arr2(n);

for(int j=0;j<n;j++)
cin >> arr[j];

vector<int>::iterator it;
for(int i=0;i<n-k+1;i++)
{
arr2=arr;
for(l=0;l<k-1;l++)
{
it = min_element(arr2.begin(), arr2.begin()+k+q);
*it=INT_MAX;

}
cout<<*(min_element(arr2.begin(),arr2.begin()+k+q))<<" ";

q++;
}


return 0;

}

[salem c]

Double posted here as well
https://www.cplusplus.com/forum/beginner/282637/

Read this -> https://www.cplusplus.com/articles/jEywvCM9/
Go and edit your other posts for readability.

[Pen72]

noted, edited

[lastchance]

- you don't need arr2
- you don't need to reconsider the whole advancing array each time - just the effect of adding a single element

[Pen72]

-If I didn't copy an extra array, wouldn't the array be affected since the value has been changed and the following iterations will go wrong.
-What function can I use to achieve it

[lastchance]

You only need to store K additional elements (in order) at any one time. A multiset would probably do that.

[Pen72]

I've modified the code using multiset the run time improved, but still time out after three test cases, what else can I do

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include<climits>
#include <bits/stdc++.h> 
using namespace std;



int main() {
    
    
    multiset<int> s; 
    multiset<int>::const_iterator it;
    int n,k;
    cin >> n >> k;
    int arr[n];
    
    for(int j=0;j<n;j++)
     cin >> arr[j];


    for(int i=0;i<k;i++)
     s.insert(arr[i]);
     it=next(s.begin(),k-1);
     cout<<*it<<" ";
    
    for(int i=k;i<n;i++)
    {   
        s.insert(arr[i]);
        it=next(s.begin(),k-1);
        cout<<*it<<" ";
    }

return 0;

}

[lastchance]

As far as your algorithm is concerned, your multiset only ever needs to hold the smallest k elements. So:
- if the proposed element you add to the set would be equal to or larger than the biggest element of the set ... then you DON'T need to insert it;
- if you do add an element to the set then you can subsequently remove the biggest element; this will keep the set small and hence quick to insert in;
- the next value that you write out will be either the last one (if nothing was inserted), the new one (if it is the smallest) or the element just one place away in the set. You don't have to iterate through a large number of values with it=next(s.begin(),k-1);


From the c++ perspective, in standard c++ the following line would (currently) be illegal:
int arr[n];
as (at the moment) a c-style array size needs to be known at compile time.

[Pen72]

I've done the first two, but not sure how to implement the last one

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include<climits>
#include <bits/stdc++.h> 
using namespace std;



int main() {

    multiset<int> s; 
    multiset<int>::const_iterator it;
    int n,k,max=INT_MIN;
    cin >> n >> k;
    vector<int> arr(n);
    
    for(int j=0;j<n;j++)
     cin >> arr[j];


    for(int i=0;i<k;i++)
    {
        if(arr[i]>=max)
         max=arr[i];
        s.insert(arr[i]);
    }
     it=next(s.begin(),k-1);
     cout<<*it<<" ";
    
    for(int i=k;i<n;i++)
    {   
        if(arr[i]>max)
         max=arr[i];
        
        if(arr[i]<=max)
        { 
            s.insert(arr[i]);
            s.erase(prev(s.end()));
            it=next(s.begin(),k-1);
         }
        
        
        cout<<*it<<" ";
    }

return 0;

}

[lastchance]

A set or multiset always sorts itself. If you make sure that you only have k elements in your multiset all the time then the kth smallest is just whichever is at the large end of the multiset.

[Pen72]

Problem solved, thank you!

[lastchance]

#include <iostream>
#include <vector>
#include <set>
#include <functional>
using namespace std;

int main()
{
   int n, k;
   cin >> n >> k;
    
   vector<int> A(n);
   for ( auto &e : A ) cin >> e;

   multiset<int,greater<int>> S( A.begin(), A.begin() + k );
   cout << *S.begin() << ' ';

   for ( int i = k; i < A.size(); i++ )
   {
      if ( A[i] < *S.begin() )
      {
         S.insert( A[i] );
         S.erase( S.begin() );
      }
      cout << *S.begin() << ' ';
   }
}