How to implement HACKRNDM using maps

I’ve implemented HACKRNDM using sort+ binary search, how should I do it using maps.
My implementation

This is not a problem for maps. But if you insist on using maps, here is a way.

Store all the values in the map and put for example true with it. This value does not matter. Now while traversing the values, use the map to check if there is a value which is k less. But avoid double counting

We need to keep a map<int,int> and lets name it as mp.

mp[i] will show the number of elements from the input array arr which have the value as i.

Then for each element num in arr(Input array) we will add mp[num+k] to our answer.
This can also be done by maintaining a count_array and incrementing that array but as there are also negative number in constraints so taking map is better.

Here is my AC solution link.Click Here


Thank you!

1 Like

if you think your question is answered please mark it accepted :slight_smile: