### dakshdixit183's blog

By dakshdixit183, history, 4 months ago,

Ternay Search is a very cool upgrade/modification on Binary Search logic There are enough resources available on this topic my favorite resource is :-

This blog will include a different implementation of the approach which I found very cool

    int l=1,r=mx;
while(r>=l){
int mid = (r+l)/2;
int m1 = check(mid);
int m2 = check(mid+1);
if(m1>=m2){
ans = updateAns(and,m1);
r=mid-1;
}
else{
l=mid+1;
ans = updateAns(and,m2);
}
}


It would make more sense if you study the concept and then solve these 2 problems these are fairly recent problems as well

Would love any input to improve this blog.

• +6

By dakshdixit183, history, 10 months ago,

You are given an array of integers arr, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.

Method 1:- Use of Priority Queue(O(nlogn)

        int n = arr.size();
vector<int> ans;
priority_queue<pair<int,int>> pq;
for(int i=0;i<k;i++){
pq.push({arr[i],i});
}
ans.push_back(pq.top().first);
for(int i=k;i<n;i++){
pq.push({arr[i],i});
while(pq.top().second<=i-k){
pq.pop();
}
ans.push_back(pq.top().first);
}
return ans;


Method 2:- Use of Maximum Queue:- In this method we mantain a queue which can tell us the maximum value of the particular Sliding Window

    int n = arr.size();
vector<int> ans;
//Implementation of Maximum Queue
deque<int> q;
while(!q.empty() && q.back()<x){        //q.back()>x(To convert to Minimum Queue)
q.pop_back();
}
q.push_back(x);
};
auto remove = [&](int x){
if(q.front()==x){
q.pop_front();
}
};
auto update = [&](){
ans.push_back(q.front());
};
//End of Implementation of Maximum Queue
for(int i=0;i<n;i++){
int j=i-k;
if(j>=0){
remove(arr[j]);
}
if(i>=k-1){
update();
}
}
return ans;


Here in Implementation I used Lamda Functions If you dont know you can use normal functins instead it works the same.

You can read about this technique in detail from CP Algorithms :- Minimum Queue The implementation there is for a minimum queue this is for a maximum queue

• +1

By dakshdixit183, history, 11 months ago,

I am doing a problem which requires similar operation in which we have to find element smaller than x then delete it from multiset then find for another x. I am using an approach that is giving TLE for 10^5 constraints