Yeah I think so and using custom hash solves the problem of collisions
1 Like
Maybe they selected elements such that collisions are maximized.
Can you do me a favour, can you run the same program with the following change? Instead of storing the number directly in unordered_map; try storing number+11223344 in unordered_map; and tell me the runtime.
1 Like
Yea. Multiple Keys in Bucket = Collision. The way unordered map resolves a collision is to do a O(n) check.
1 Like
Are You Saying to do this?
lastind[a[j] +11223344 ]=j;
i=max(i,lastind[a[j]+11223344]+1);
ans=max(ans,j-i+1);
lastind[a[j]+11223344]=j;
Try it (Not sure if it will work, but think it will)
1 Like
I did this but itâs Giving TLE
As the others said, itâs probably because that collisions are not very common in a hash map. There will be collisions only if we deliberately set such test data. And here it looks like the setters didnât really want to block out hash map solutions.
@c2h5sh My unordered_map solution gave a TLE here while map passed. Maybe you can try this problem.
@dardev These are my submissions for the above problem.
Unordered_map - TLE.
Map - AC.
2 Likes
yes if there is such a test data which results in collisions then neither unordered_map nor map passes in this problem.
@aman_robotics,As you are the author of the problem,Can You guide us with this doubt.
1 Like
Interesting, and it consumes time to implement a custom hash (unless templated). I suppose it is better to try Unordered_Map and Map and see what works.
2 Likes
Yep. Thatâs the only solution I guess. But there is that penalty for wrong submission in some short contests. 
.
2 Likes
and if neither works then? Just like in this question(if there comes a test case where it may lead to collisons.)
Then you will have to implement custom hash and use unordered_map or you can use array compression and unordered_map
1 Like
Multiple Keys in a bucket means multiple keys which are all same?
like if we are inserting a value say,1e9 so many times, then it will lead to collisions.Right?
Do You mind if you can guide me how custom hash can be implemented or the word you used âarray Compressionâ?
1 Like
No. It means multiple keys have same hash. So k1 and k2 have same hash, so we are unable to resolve whether particular key is k1 or k2 without doing a linear search.
1 Like
Are you trying to say like this?
if k1 has value 2
k2 has value 2
so we are unable to resolve whether particular key is k1 or k2 without doing a linear search.
Am I right?
User Defined Hash: How to create an unordered_map of user defined class in C++? - GeeksforGeeks
1 Like
Y
Yes. So k1 and k2 are colliding. Now imagine if there was a second hash function which resolves k1 and k2 differently. So if the first one collides, we can use the second.
1 Like