I was trying to the this question and during that, I used the following code.
void solve() {
read(n); read(x);
map<int,int>mp;
for(int i = 0; i< n; i++){
int a; cin>>a;
if(mp.find(a) != mp.end()){
int b = mp[a]+1;
cout<<b<<" "<<i+1<<endl;
return;
}
else{
mp[x-a] = i;
}
}
cout<<"IMPOSSIBLE"<<endl;
}
this did not give any tle error but when i used the following code
void solve() {
read(n); read(x);
unordered_map<int,int>mp;
for(int i = 0; i< n; i++){
int a; cin>>a;
if(mp.find(a) != mp.end()){
int b = mp[a]+1;
cout<<b<<" "<<i+1<<endl;
return;
}
else{
mp[x-a] = i;
}
}
cout<<"IMPOSSIBLE"<<endl;
}
it was giving tle in the test cases 23 and 24. now I know that both of them are the same except for the use of data structure, but the map should be slower than unordered_map but the opposite is true, why is this happening can anyone explain?
Auto comment: topic has been updated by ErenZ (previous revision, new revision, compare).
find fuction causes tle in this case ,instead of (mp.find(a) != mp.end()) use (mp[a]>0) and also change else statement like this mp[x-a]=i+1 , so that after all mp[a] will be 0 if value is not inserted,and it will easily checked in program.
btw, map uses tree structure to find a element while unordered map search element by visiting every element in it .
Complexity for ordered map is always O(log(N)) for accessing values..but in unordered map we cant say anything..at worst case even it can go upto O(N)..so generally i prefer to use ordered map to avoid such TLE's
thanks for replying, Is there some article that explains how this complexity of the unordered_map works? I thought it was always O(1).
in ordered map elements are stored in increasing order ..so when you try to access elements you can think similar of binary search so O(log(N)) ..but in unordered map elements are in random order (can even differ from order of insertion) so when accessing elements you can think of linear search so O(N) at worst case...my POV
Blowing up unordered_map, and how to stop getting hacked on it
thanks this was very helpful and i learned about hashing
me (!)