Getting tle by using unordered map but ac using map

Problem link :
Solution using unordered map :
Solution using map :

1 Like

I was talking about the same thing right here.
We have to use a custom hash, if we are using unordered map. It reduces collision probability.


It is this because, when unordered map runs out of contguous space so it takee O(n) time to shift all the elements to a new space ?

see the differences in these codes, in one code he just reserved memory for his unordered map.


so this mean we should use map always??

it depends on the situations we need to implement it.

If O(logn) operation on the map is within bounds, then use map. If you need a HashMap for a faster look up, use custom hashing and reserve memory for the unordered_map as @anon41069019 has mentioned.

1 Like

okk thanks

Map takes O(Logn) time in worst case
Unordered map takes O(1) time in best case and O(n) Time in Worst case

It can also blow up to O(n^2) I guess. When there are rehashing and reallocation of space.

I never understood this concept named “blow up to O(n^2)” in Unordered map what does it actually mean and why does it happen can you explain?

I am not very familiar with the implementation of unordered_map in C++ stl. But apparently, one can easily build a test case to make the map run into O(n) collisions. And as the number of elements/collisions increase, with each insertion it will change the hash function it uses (the prime it chooses for MOD I guess), recompute the hashes for all the elements, and reallocates them, thus costing you a lot of time. More on this here.

The last paragraph (just before the custom hashing solution), he has explained how one can make test cases to blow up a hash map.

Yeah i have seen this link before and read it too but the writer of this blog was so much into technicality that i couldn’t understand anything.

Haha, even I don’t understand much of it. But the only way to gain more knowledge on this is to dig deep into the stl implementation. Until then, lets stick with map.

1 Like

Yes i always use map now instead of unordered_map.

1 Like

I’ve implemented MinHeap in , but it’s giving TLE at Testcase “5”. (link:
{ I’m not getting the logic used in editorial for this problem :frowning: }

Any kind of help will be truly appreciable :slight_smile:

{Logic used in minHeap:

For i such that a[i]%k!=0, store minimum difference (a[i]//k+1)*k - a[i] in heap and than sequentially travel from x=0 until heap beacome empty, solving for “top of heap” in each iteration. If at any time the top is less than x, than increase that top to (top+k). The logic is working but giving TLE at TC 5 :frowning: