CF Step
Youtube Linkedin Discord Toggle Dark/Light/Auto mode Toggle Dark/Light/Auto mode Toggle Dark/Light/Auto mode Back to homepage

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
    # 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)).

Read this blog by FAT_ to find out more