Maximum. element in every window

#1

how the time complexity is o(n) because there is while loop also and it can run to k times so o(nk) would be the complexity… can anyone explain it in simpler way…

#2

@shampblocks
hello Shubham,
we can observe that every element of array is added and removed from deque at most once. So there are total 2*n operations in overall process.
therefore time complexity is O(n)

#3

And what about second whole loop which is checking a[i]>=a[q.back]??

#4

@shampblocks
image

second loop is also popping out the inserted element right ?
total n insertion will be there in the complete process.

so both loop will run atmost n time in whole process.

1 Like
#5

How to find time complexity by mathematically in these types of questions??

#6

it is tough to frame any recurrence relation for this problem .thats why i have given observation based answer

#7

But sir i am. Facing problem in getting intution that it will run o(n) because for every I from 0 to n -1 it is doing push back which is o(1) also there is loop which remove elements which are lesser then that and also romoving element which is balancing window so more then o(1) operation happening… Can u correct if I m wrong…

#8

operation is happening on a single queue right?

and in queue we can have n element at max

also if any element get popped from queue then it will never be considered in any future operations right?

for each element in an array we are performing only 2 operation-> 1 to insert from queue and 2 to pop element from queue thats why 2*n operation in total for n elements

1 Like
#9

now I got it thanks sir…

#10

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.