Quirks of Non Existent Map Elements
Consider this simple code.
str = "abc"
map<char, int> freq
for ele in str:
fre[str[i]] += 1
for ch in ['a', 'z']:
if freq[ch] > 0:
cout << ch << " exists in the map"
cout << "unique characters is " << freq.size()
What is the count of unique characters printed at the end?
You might think it’s 3, but it’s actually 26. Why? Because if you try to access a non existent element in a map, the element gets created in the map and initialized to its zero value. When dealing with characters, be very careful about accessing non existent element if you rely on the map’s size at any point in the code. What’s the proper way then?
if mp.find(key) != mp.end():
# element exists. do something
else:
# element doesn't exist, do another thing
What if you aren’t dealing with characters or the map’s size? Is it safe to directly access map elements without checking for existence? Solve this easy Div 3 problem to find out for yourself : CF1029D : Concatenated Multiples
This was my initial code. Submission
for (int i = 0; i < n; i++) {
for (int len = 1; len <= 10; len++) {
int need = something
ans += md[len][need];
}
}
However, this resulted in TLE, taking more than 2 seconds to execute. This comment from heello had interesting insights to offer on why that is the case. Quoting him
If u simply do ans += mark[digits][requiredmod]; then even though that required mod doesn’t exist in the map, then also it will be added to that map and now the size of the map = (actualsize+1), and if you do this n*10 times the size of the map would increase and therefore the time to search as well
So it’s clear what’s happening here, since n is already 2*10^5 and we are also dealing with modulo operations here, we can’t take the time limit for granted. With the above code, the size of the map can grow to 10*n at the end of the process, since we insert an element into the map if it doesn’t exist. Hence, this can lead to TLE issues where the time limit is tight.
Modifying it to
for (int i = 0; i < n; i++) {
for (int len = 1; len <= 10; len++) {
int need = something
auto &mp = md[len];
if (mp.find(need) != mp.end()) {
ans += mp[need];
}
}
}
brings down the runtime to 0.6 seconds. Submission
Finally, a quirk related to existent elements in multisets.
multiset<int> mset
// Insert elements
if(mset.count(1)) {
cout << 1 << " exists"
}
What is the time complexity of mset.count(1)? Is it O(log(n))? It’s not. It’s actually O(freq(1)).