Find maximum of minimum for every window size k in a given array.

0 votes
asked in Interview Question by admin
Find maximum of minimum for every window size k in a given array.
Add question to:

1 Answer

+1 vote
answered by allenite
edited by admin

Using self-balancing binary search tree

#include<bits/stdc++.h>
using namespace std;
main()
{
    int n,k,a[100009],i;
    multiset<int >s;
    multiset<int >::iterator mi ;
    multiset<int >::iterator ma ;
    cin>>n>>k;
    for(i=0;i<n;i++)
    {
        cin>>a[i];
        if(i<k)
            s.insert(a[i]);
    }

    for(i=k;i<n;i++)
    {
        mi=s.begin();
        ma=s.end();
        ma--;

        cout<<"minimum "<<*mi<<" ";
        cout<<"maximum "<<*ma<<" ";
        s.erase(s.find(a[i-k]));
        s.insert(a[i]);
        cout<<"\n";
    }
    mi=s.begin();
    ma=s.end();
    ma--;
    cout<<"minimum "<<*mi<<" ";
    cout<<"maximum "<<*ma<<" ";
    cout<<"\n";

}

 

commented by allenite
We can also do this using
1) min heap and max heap
2)deque doubly ended queue
...