Best in JAVA solution T.C. => O(n) Using Dequq ; By : Shashank

google
programming
amazon
interview-questions
Tags: #<Tag:0x00007f2426369d58> #<Tag:0x00007f2426369bf0> #<Tag:0x00007f2426369a60> #<Tag:0x00007f2426369920>

#1

int n=A.size();
if(n<=1){
ArrayListans=new ArrayList<>();
ans.addAll(A);
return ans;
}
Dequedq=new LinkedList<>();
ArrayListans=new ArrayList<>();
int i=0;
for( ;i<B;i++){
while(!dq.isEmpty() && A.get(dq.peekLast())<=A.get(i)){
dq.removeLast();
}
dq.addLast(i);
}
for( ;i<n;i++){
ans.add(i-B,A.get(dq.peekFirst()));
while(!dq.isEmpty() && dq.peekFirst() <= i-B){
dq.removeFirst();
}
while(!dq.isEmpty() && A.get(dq.peekLast())<=A.get(i)){
dq.removeLast();
}
dq.addLast(i);
}
ans.add(i-B,A.get(dq.peekFirst()));
return ans;
Done By : Shashank;