Hash Maps for Quant Interviews: The Two Sum Problem in C++

In the article of today, we talk about an interview question, simple on the surface, that’s given quite a lot as interview question for quants positions: the two sum problem.

What is the two sum problem in C++?

🔍 Problem Statement

Given a list of prices and a target value, return all the indices of price pairs in the list that sum up to the target.

Example:

nums = {2, 7, 11, 15}, target = 9  

Output: [{0, 1}] 

// because nums[0] + nums[1] = 2 + 7 = 9

1. The Naive Implementation in [math] O(n^2) [/math] Time Complexity

The simple way of doing is to loop through the list of prices twice to test every possible sums:

std::vector<std::pair<int, int>> twoSum(const std::vector<int>& nums, int target) {
    std::vector<std::pair<int, int>> results = {};
    for (int i = 0; i < nums.size(); ++i) {
        for (int j = i + 1; j < nums.size(); j++) {
            if (nums[i]+nums[j] == target){
                results.push_back({i, j});
            };
        };
    };
    return results;
}

This can be used with the list of prices given in our introduction:

int main() {
    std::vector<int> nums = {2, 7, 11, 15};
    int target = 9;
    auto results = twoSum(nums, target);

    for (const auto& pair: results) {
        std::cout << "Indices: " << pair.first << ", " << pair.second << std::endl;
    };


    return 0;
}

Running the code above prints the solution:

➜  build git:(main) ✗ ./twosum
Indices: 0, 1

The time complexity is [math] O(n^2) [/math] because we’re looping twice over the list of prices.

And that’s it, we’ve nailed the two sum problem in C++!

But…. is it possible to do better?

2. The Optimal Implementation in [math] O(n) [/math] Time Complexity

The optimal way is to use a hash map to store previously seen numbers and their indices, allowing us to check in constant time whether the complement of the current number (i.e. target - current) has already been encountered.

This reduces the time complexity from O(n²) to O(n), making it highly efficient for large inputs.

std::vector<std::pair<int, int>> twoSumOptimized(const std::vector<int>& nums, int target) {
    std::vector<std::pair<int, int>> results = {};
    std::unordered_map<int, int> pricesMap;
    for (int i = 0; i < nums.size(); ++i) {

        int diff = target - nums[i];

        if (pricesMap.find(diff) != pricesMap.end()){
            results.push_back({pricesMap[diff], i});

        } 
        pricesMap[nums[i]] = i;

    };
    return results;
}

And we can run it on the exact same example but this time, it’s O(n) as we loop once and hash maps access/storing time complexity are O(1):

int main() {
    std::vector<int> nums = {2, 7, 11, 15};
    int target = 9;

    auto results = twoSumOptimized(nums, target);

    for (const auto& pair: results) {
        std::cout << "Indices: " << pair.first << ", " << pair.second << std::endl;
    };

    return 0;
}

3. A Zoom on Unordered Hash Maps in C++

In C++, std::unordered_map is the go-to data structure for constant-time lookups. Backed by a hash table, it allows you to insert, search, and delete key-value pairs in average O(1) time. For problems like Two Sum, where you’re checking for complements on the fly, unordered_map is the natural fit.

Here’s a quick comparison with std::map:

Use unordered_map when:

• You don’t need the keys to be sorted
• You want maximum performance for insert/lookup
• Hashing the key type is efficient and safe (e.g. int, std::string)

Let me know if you’d like to add performance tips, custom hash examples, or allocator benchmarks.

The code for the article is available here:

https://github.com/cppforquants/twosumprices