new_algos's blog

By new_algos, history, 2 years ago, In English

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

 
 
 
 
  • Vote: I like it
  • +13
  • Vote: I do not like it

»
2 years ago, # |
Rev. 2   Vote: I like it -12 Vote: I do not like it

[Edit: oops, I misread.]

»
2 years ago, # |
Rev. 8   Vote: I like it +4 Vote: I do not like it

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 one
idea number two, probably wrong
»
2 years ago, # |
  Vote: I like it +18 Vote: I do not like it

Am i missing something or can we just use two heaps?

  • »
    »
    2 years ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    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)?

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        How using just heaps (not sets) remove concrete element?

        • »
          »
          »
          »
          »
          2 years ago, # ^ |
            Vote: I like it +8 Vote: I do not like it

          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.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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
  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    But here, elements can be repeated, so multiset can be a better option.

»
5 weeks ago, # |
  Vote: I like it -11 Vote: I do not like it

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.

Code

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

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +29 Vote: I do not like it

    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

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it +10 Vote: I do not like it

    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 keys

    8- Because you're only using $$$1$$$ and $$$0$$$ as values, you can just use a std::multiset instead

    9- 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 of map<ll,bool>::iterator it

    12- It's very hard to read the code when it has no indentation.