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
Honestly, I can't come up with an elegant solution, so I'll tell a couple of slightly data-structure-heavy ones instead.
Implicit 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)).
First 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
Am i missing something or can we just use two heaps?
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.
just put the link
It can be solved easily in O(n) using hash map. Also code will be pretty simple
Approach
Make 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..k
iterator 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 previsouly
hash[arr[i]]=1;
set iterator it=hash.begin()+mid;
cout<<(*it).first<<"\n";
Time/Memory Complexity Analysis
Time-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 map
Hash 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.
Sorry for long comment
Tip- 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 compile
2- stl map is not a hash map
3- you cant sum an iterator in a map
4- if it was actually a hashmap it wouldnt maintain the order so you cant find the median by doing hash.begin()+mid
5- this is a 2 year old blog
6- You can't remove an element in a hashmap with
hash[key]=0;
. You need to callhash.erase(hash.find(key))
. Also please name your variables something that doesn't clash with things in the global namespace, likestd::hash
.7- Fails if there are duplicate keys
8- 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<ll,bool> it
instead ofmap<ll,bool>::iterator it
12- It's very hard to read the code when it has no indentation.