Below you can find the code that we will be reviewing today. Before you scroll down to section where I fix it, feel free to check how many mistakes you can find.

using namespace std;

vector<size_t> ContainsTwoSum(vector<uint8_t> input, uint8_t &target)
{
    unordered_map<uint8_t, size_t> m;

    for (int i=0; i<input.size(); i++) {
        uint8_t complement = target - input[i];

        if (m.find(complement) != m.end()) {
            return {m[complement], i};
        }

        m[input[i]] = i;
    }

    return {};
}

This is a solution for one of the variants of the popular algorithmic tasks: given a vector of 1-byte unsigned integers and a 1-byte unsigned integer target value, return the indices of the two numbers that add up to the target. Although the code compiles and works properly, there’s a lot to do in terms of its quality. Let’s start with the first line:

using namespace std;

This is never a good idea. std is a huge namespace and chances that one of the types defined within std namespace will collide with some other type are pretty big. You should always use std:: explicitly whenever you use something from the standard library. The next is function’s signture:

vector<size_t> ContainsTwoSum(vector<uint8_t> input, uint8_t &target)

There are couple of thigs to consider here:

• What do we return here? In general a vector of two indices, but what if sum doesn’t exist? Do we return empty vector? A vector of two invalid numbers? The situation seems to be “all or nothing”, either there is a sum or there isn’t, but how will we communicate to the user of this API that some vectors mean “sum does not exist”? When such questions appear, it is most probably a good idea to use std::optional. By introducing it in a function signature, we tell the user “either there will be a vector of two indices or there will be no vector at all – you must check it first”.
• The input vector is passed by mutable value. Do we really need to modify this vector inside the function? Do we really need to copy vector to pass it to the function? The answers for both of these questions seem to be “no”, so it’s a good idea to pass it by a const reference.
• The last thing is target sum passed by reference. Despite the fact that it will prevent us from providing a number directly in the function call (e.g. ContainsTwoSum({}, 12U)) because the compiler won’t be able to bind non-const lvalue reference to our rvalue 12, it also does not make sense from the efficiency point of view. Addresses are typically 32 or 64 bit (depending on the architecture), so by passing 1-byte input argument we are effectively increasing its size to 4 or 8 bytes. This is why it is better to pass primitive types by value, not by reference.
  After all these considerations, we end up with the following function signature:

std::optional<std::vector<size_t>> ContainsTwoSum(const std::vector<uint8_t> &input, const uint8_t target)

Next there’s an unordered map declaration:

unordered_map<uint8_t, size_t> m;

What is m? What do we save by giving such a short, non-expressive name? We definitely loose readability and maintainability of the code. Don’t be afraid of longer variable names and always make them self-explanatory. Here we could go for something like:

std::unordered_map<int16_t, size_t> number_to_index_mapping;

After that we have a for loop.

for (int i=0; i<input.size(); i++)

What are we iterating over? Over the indices of the vector. Indices are of type size_t which is an unsigned integer what means that we have an implicit conversion here. To avoid it, we correct the type of i:

for (size_t i=0U; i<input.size(); i++)

Now let’s look at the very interesing line:

uint8_t complement = target - input[i];

Three things in here:

• complement is calculated and then saved what means that it is not modified anywhere. It means that it should be marked const.
• There are unsigned integers everywhere in this function, so someone put it here as well, but target may be equal to e.g. 2 and num[i] may be equal to 3. What is the result of 2-3 when stored in a 1-byte unsigned integer? 255 because of underflow error! To correct this, we must change that type to a signed integer. What size should it be? Well, the lowest value of the target could be 0 and the highest value of the vector element could be 255, so we need a type which can hold -255 value, which is int16_t (int8_t lowest value is -128, so 0-255 would give us 1).
• Accessing vector member with square brackets is a bad practice and at() should be used instead. If you accidentally go beyond the vector size, at() will throw an exception which you can catch and handle somehow, but if you go beyond the vector size using square brackets, you get a segmentation fault and there’s nothing you can do about it. Some could say that at() causes performance overhead because it has to additionally compare the index with the vector’s size. I would say that you must have a really good reason to not to use at() (for example, results from a profiling tool showing that at() calls are the real bottleneck in your algorithm).

Combining all these 3 points together, we get the following line:

const int16_t complement = target - input.at(i);

The next in line is the if statement checking presence of a complement in the map:

if (m.find(complement) != m.end()) {
    return {m[complement], i};
}

Firstly, when we want to check if a key exists in the map, find is ok, but the because it has to be compared to the end iterator, the statement becomes unnecessarly long. To make it shorter, we can use count function which returns the number of occurrences fo the given key and thus every number greater than 0 will be evaluated to true. Both find and count have time complexity O(1), so the change does not impact the overall performance.

Secondly, accessing map member with square brackets brings the same problems as accessing vector elements described above. Map also delivers at() member function, so let’s just use it here.

As the last step, we need to adjust returned value to the new function’s signature basing on the std::optional.

if (number_to_index_mapping.count(complement)) {
    return std::vector<size_t>{number_to_index_mapping.at(complement), i};
}

At the end, we have a line adding an element to the map which can be rewritten using insert() member function:

number_to_index_mapping.insert({input.at(i), i});

Note for beginners: When assigning values to a map, remember that insert() and [] are not equivalent! The insert() method adds a key-value pair to the map only if the key does not already exist in the container. This means insert() will not overwrite an existing value for a key. In our case it doesn’t matter, but if you need behavior where the value for an existing key should be updated, you should use the [] operator.

Eventually, we end up with the whole function looking like this:

std::optional<std::vector<size_t>> ContainsTwoSum(const std::vector<uint8_t> &input, const uint8_t target)
{
    std::unordered_map<int16_t, size_t> number_to_index_mapping;

    for (size_t i=0U; i<input.size(); i++) {
        const int16_t complement = target - input.at(i);

        if (number_to_index_mapping.count(complement)) {
            return std::vector<size_t>{number_to_index_mapping.at(complement), i};
        }

        number_to_index_mapping.insert({input.at(i), i});
    }

    return std::nullopt;
}