### new_algos's blog

By new_algos, history, 10 months ago, ,

You are given an array of n integers. Your task is to calculate the median of each window of k elements, from left to right.

The median is the middle element when the elements are sorted. If the number of elements is even, there are two possible medians and we assume that the median is the smaller of them.

1≤k≤n≤2⋅105

1≤xi≤109

• +13

 » 10 months ago, # | ← Rev. 2 →   -12 [Edit: oops, I misread.]
 » 10 months ago, # | ← Rev. 8 →   +4 Honestly, I can't come up with an elegant solution, so I'll tell a couple of slightly data-structure-heavy ones instead. idea number oneImplicit treaps support insertion in O(log(n)), deletion in O(log(n)) and access in O(log(n)). Keep the sorted window in the implicit treap, adding and removing elements upon each movement, and simply access the middle element every time.How to keep it sorted? Insert elements using binary search.Complexity is O(n * log^2(n)). idea number two, probably wrongFirst off, compress the values in the array.Then maintain an array A[N], where A[i] denotes the number of compressed elements in the window not less than i.When moving a window, you'll have to subtract 1 from some suffix and add 1 to another suffix. This can be done with sqrt decomposition or an RMQ segment tree with range addition.When searching for the answer, find the leftmost position whose value is not less than k / 2 and "decompress" it.Complexity is O(n * sqrt(n)) or O(n * log(n)).
•  » » 9 months ago, # ^ |   +5 More or less the same as your first idea but you can use ordered_set there so you don't have to implement almost anything.
•  » » 9 months ago, # ^ |   +3 Thanks , Solved using implicit treap.
 » 9 months ago, # |   +18 Am i missing something or can we just use two heaps?
•  » » 9 months ago, # ^ | ← Rev. 3 →   0 I think there is need for clarification.I see two heaps as:1) build two sets (size of k / 2 and k — k / 2) for a[1..k]. Elements of first set will be not greater than elements of second.2) for shifting window by 1 to the right, we need to hold sets of that size.3) Then for each step answer is biggest element of first set.Cool idea for O(nlogn). But maybe there is need for O(n)?
•  » » » 9 months ago, # ^ |   0 Heaps have a pretty small constant so it should pass. Everything i can think of involves keeping a sort in some way, so I can't really think of an O(n) approach.
•  » » » » 9 months ago, # ^ |   0 How using just heaps (not sets) remove concrete element?
•  » » » » » 9 months ago, # ^ |   +8 maybe use two heaps, heap 1 save the original elements, heap 2 save the deleted elements. When you insert an element push it into heap 1.When you remove an element push it into heap 2.When you pop the biggest/smallest from the heap, if the element on the top of heap 1 is the same as the top of heap 2, then remove this element from both heaps. Keep on removing until heap 1 is empty/found an element which is in heap 1 but not in heap 2.For same elements you can tie it with an id, and the id must be different.
 » 9 months ago, # |   0