The problem statement is pretty straight forward: given an array of integers and a window size, return an array of doubles of the median of each window.

arr = 1, 3, 5, 10, 6, 9, 2

k = 3

would yield a result of 3, 5, 6, 9, 6

Using std::priority_queue (in C++) for the heap implementation, there's a minHeap and maxHeap. In a single iteration, insert the value entering our window in the correct heap, rebalance as necessary, add the median to the result (if the window is big enough), then remove the value which is leaving the window from whatever heap it's in: This could require moving all but 1 heap element to the other heap, then moving them back.

The lesson I saw this on actually inherits from priority queue and implements remove functionality: Linear search [O(k)], then removes the item [O(log k)]. It claims O(n * k) complexity as at each iteration the insertion is O(log k) and the search to remove is O(k). I assume in an interview extending a heap beyond it's traditional form is not only unnecessary but probably frowned upon.

I'm curious of the complexity at which the version w/o the direct removal would run. The O(n) part is obvious but the sub operations not as clear to me. A heap will generally have k/2 items in it. In the worst case you delete [O(log k)] and then insert [O(1)] each one. My mind is telling me O(n * k log k) but I wouldn't bet my house on it.

For the record: Not looking for an optimal solution - just the runtime of this one.


  if maxHeap is empty or maxHeap.top > num:
    push num on maxHeap
    push num on minHeap

  // rebalance
  if maxHeap.size > minHeap.size + 1:
    move maxHeap.top to minHeap
  else if minHeap.size > minHeap.size
    move minHeap.top to maxHeap

get Median:
  if maxHeap.size == minHeap.size:
    return maxHeap.top + minHeap.top / 2.0
  else if maxHeap.size > minHeap.size 
    return maxHeap.top
    return minHeap.top


  if maxHeap.top >= num:
    move maxHeap.top to minHeap until maxHeap.top == n;
    remove maxHeap.top
    move minHeap.top to maxHeap until balanced
    move minHeap.top to maxHeap until minHeap.top == n;
    remove minHeap.top
    move maxHeap.top to minHeap until balanced

findSlidingWindowMedian(arr, k):
  // This is where the mystery is.  Worst case we have to remove
  // a number at the bottom of a k/2 sized heap.  So that would be
  // log k for k/2 operations then O(1) for k/2-1 operations?
  left = 0
  for right = 0 to arr.size

    if right >= k-1
      add median for current window to result 
      left += 1

  return result
  • 1
    $\begingroup$ I'm confused by the question. Can you replace the "Using.." and "The lesson.." paragraphs with a clear description of the algorithm you want to know the runtime of? I suggest using concise pseudocode. Right now it reads like "here's one algorithm, but wait, that's not what I want to know about, I want to know the runtime of some variant" - and I don't understand exactly what either the first algorithm or the variant is. No need to describe other versions that you don't want analyzed; it suffices to describe the one algorithm you do want to analyze. $\endgroup$
    – D.W.
    Jan 12, 2020 at 21:02
  • $\begingroup$ Can you please sketch the version w/o the direct removal explicitly? I don't "see" it. $\endgroup$
    – greybeard
    Jan 12, 2020 at 22:48
  • $\begingroup$ (I do "see" use of a self-balancing order-statistics tree.) $\endgroup$
    – greybeard
    Jan 12, 2020 at 22:54
  • $\begingroup$ I've updated the post w/ the entire code (which is kind of wordy). 90% of it is keeping track of the heaps. I forgot if you're not brushing up on interview skills this stuff can get a bit abstract. $\endgroup$ Jan 13, 2020 at 14:47
  • $\begingroup$ Sorry, but we discourage code on this site. Please replace the code with concise pseudocode. Many people here might not read C++ code; and code tends to be a lot more verbose than necessary to present the algorithm. $\endgroup$
    – D.W.
    Jan 13, 2020 at 17:58

2 Answers 2


Store the window in a balanced binary search tree. Each time a value arrives, add it to the tree, remove the one leaving the window, compute the median, and output it. Each of those operations can be done in $O(\log k)$ time, so the total running time to process $n$ items will be $O(n \log k)$.

  • $\begingroup$ Thanks. I failed to mention that this module was about hitting things w/ a 2-heap approach, so was more curious about the run time of that. $\endgroup$ Jan 12, 2020 at 20:04
  • $\begingroup$ @kiss-o-matic, that doesn't appear in your problem statement, so I suggest you edit your question to state that clearly and credit the original source or context where you encountered this task. $\endgroup$
    – D.W.
    Jan 12, 2020 at 20:32

It’s easier to figure out if k is large, say k = 100.

You start by creating two heaps with 50 elements each, one with the 50 smallest of the first 100 numbers with fast access to the largest one, and one with the 50 largest, with fast access to the smallest one. The median of all 100 items can be found in O(1).

Now you move the window by one position. Element #0 is removed from its heap, element #100 is added to its heap. Then if you are lucky you have two heaps of size 50, if you are unlucky you have one heap of size 49 and one of size 51, and move either the largest of the small numbers, or the smallest of the large numbers, from its heap to the other heap.

For odd k both heaps need a size that is different by one and the heap with the largest number of elements contains the median. For example k=99, your two heaps must contain 49 and 50 elements. If you are unlucky moving the window results in 48 and 51 items and you move one item over.

Since accessing the second element is also quite fast, you can allow a slightly larger size difference of the heaps which may save some insertions.

And you need O(n log k) operations.

PS. Figured out that you can’t delete an arbitrary item from a heap. So you need to keep track of where your k elements in the window are in the heap, but that doesn’t make things much harder. Still O(n log k).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.