educative.io

[Runtime analysis] Using maxheap instead of a dequeu, for max in sliding window?

Courses
,
#1

I was wondering, if instead of using a deque for our currentwindow variable, we used a MaxHeap, where we just store the values, would the runtime then be O((n-k+1)* 2log(w))? Since for every window we would be inserting the new value and removing the old value from the heap? Simplifies to O(nlog(w)).
Just wanted to make sure/ check my answer/understanding

Course: Grokking Coding Interview Patterns in JavaScript - Learn Interactively
Lesson: Find Maximum in Sliding Window - Grokking Coding Interview Patterns in JavaScript

#2

Hello @Enki1,

Your analysis is accurate, and this approach would solve the maximum number in a sliding window problem with a MaxHeap. There’s a small fix that needs to be made. Instead of O((n-k+1) * 2log(w)), it would be O((n-w+1) * 2log(w)), which simplifies to O((n - w) log(w)).

As your analysis indicates, the MaxHeap approach would be less efficient than a deque and, hence, would not be the preferred option in the general case.

If you have any more questions or need further clarification, please let us know.

Happy learning!

1 Like