### new_algos's blog

By new_algos, history, 2 years 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  Comments (17)
 » 2 years ago, # | ← Rev. 2 →   [Edit: oops, I misread.]
 » 2 years ago, # | ← Rev. 8 →   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)).
•  » » 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.
•  » » Thanks , Solved using implicit treap.
•  » » give code ban ei
•  » » » vãi :)))))))
 » Am i missing something or can we just use two heaps?
•  » » 2 years ago, # ^ | ← Rev. 3 →   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)?
•  » » » 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.
•  » » » » How using just heaps (not sets) remove concrete element?
•  » » » » » 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.
 »
 » I used ordered_set to solve this question at the end. Insert the first k elements to ordered_set Print the first median, simply by calling find_by_order to get the value at index (k+1)/2-1 Then, for i..n-k, erase the previous number and insert the next number at index i+k, and perform the same action to print the median
•  » » But here, elements can be repeated, so multiset can be a better option.
 » It can be solved easily in O(n) using hash map. Also code will be pretty simpleApproachMake empty hash map (use STL hash map)Iterate 0..k-1 (using 0-based indexing)Set hash[arr[i]]=1;// Now set no mid as if(k%2){// odd mid=(k-1)/2;} else{.//even // As use mentioned in case of even we taking left midpoint mid=(k/2)-1;.}// Print for 0..kiterator it=hash.begin()+mid;cout<<(*it).first<<"\n";Then iterate k..n-1 (again using 0-based indexing) set hash[arr[i-k]]=0 // Remove element which is not in now window ie (i-k)+1..i (inclusive also including ends)set hash[arr[i-k]]=0;// add new element i which is not included previsoulyhash[arr[i]]=1;set iterator it=hash.begin()+mid; cout<<(*it).first<<"\n"; Time/Memory Complexity AnalysisTime-O(n) As we iterating 0..k then n-k times that changes into n-1 times we remove small factors so We left with O(n)Memory- Using hash map and storing data in it take O(n) space on average Issue with hash mapHash map works well but also need to note in worst case it take O(n) time. I checked on ideone for input 10^6 it takes 0.97 sec.Also hash map memory complexity is O(n) on average but interally it take lot more memory than You can imagine. I checked on ideone for input 10^6 it takes 93.5 kb. Code// Definations anf including stuff #include #include using namespace std; #define ll long long // Main function int main(){ ll t; cin>>t; while(t--){//Shortcut to iterate t times ll n,k; cin>>n>>k; ll arr[n]; // We can also use int but i like long long also to be safe from integer overflow // taking input for(ll i=0;i>arr[i]; ll mid; // Set mid if(k%2==0){ //even mid=(k/2)-1; } else{ // odd mid=(k-1)/2; } map hash; // First window for(ll i=0;i::iterator it=hash.begin()+mid; // As output formatting is not specified i am using spaces between numbers cout<<(*it).first<<" "; // Now itearate k..n for(ll i=k;i it=hash.begin()+mid; // Print again seprating numbers by space cout<<(*it).first<<"\n"; } } return 0; } Sorry for long commentTip- Dont copy code intstead I would suggest you to write your own code. You can take help of my code if you are stuck anywhere
•  » » 1- your code doesnt even compile2- stl map is not a hash map3- you cant sum an iterator in a map4- if it was actually a hashmap it wouldnt maintain the order so you cant find the median by doing hash.begin()+mid5- this is a 2 year old blog
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   6- You can't remove an element in a hashmap with hash[key]=0;. You need to call hash.erase(hash.find(key)). Also please name your variables something that doesn't clash with things in the global namespace, like std::hash.7- Fails if there are duplicate keys8- Because you're only using $1$ and $0$ as values, you can just use a std::multiset instead9- Your if-statement for the midpoint is unnecessary. It's equivalent to mid = (k-1)/2 which you're using in the else part anyway.10- Why are you using local, variably-sized arrays? It's much better to use global arrays, and variably sized arrays aren't even supported by the C++ Standard.11- Near the end you did map it instead of map::iterator it12- It's very hard to read the code when it has no indentation.