Two Sum Problem Solution in C++ in O(n)

The “Two Sum Problem” is described as follows:

Given an array of integers nums and an integer target, return the indices of the two integers in nums such that they add up to target. See Leetcode “Two Sum Problem”

A solution with a time complexity of \(O(n)\) in pseudocode solution looks like this:

1
2
3
4
5
6
7
8
9
10
11
12
13
14

array nums // contains random number of elements
target

array result_indices
set partial_sums
map indices_map

for i in len(nums):
    n = nums[i]
    if target - n is in partial_sums:
        result_indices.add(i)
        result_indices.add(indices_map[target - n])
    partial_sums.add(n)
    indices_map[n] = i

Iterate once over all elements in nums.

• Check if the partial sum target - n is in partial_sums. If this is the case a matching pair whose sum results in target was found, because n + targer - n = target. If target - n is in partial_sums its index is also in indices_map therefore the index pair can be added to result_indices.
• Add n to partial_sums (such that it can be found in a subsequent iteration).
• Add the index i of n to indices_map (such that it can be found in a subsequent iteration).

The output of this solution is the array result_indices which contains index pairs that result in target. If result_indices is empty no solution was found. It is obvious why this solution runs in \(O(n)\) because each element of nums is only accessed once and the containers partial_sum and indices_map have insert and access complexities of \(O(1)\).

A possible solution in C++ (17) looks like this:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;

class Solution {
    public:
    vector<int> twoSum(vector<int>& nums, int target) {
        // find indices
        vector<int> result_indices;
        unordered_set<int> partial_sums;
        unordered_map<int, int> indices_map;

        // iterate once over all elements in nums
        for (size_t i = 0; i < nums.size(); i++) {
            int n = nums.at(i);
            // check if the target minus the current element is in the set sums
            // if that is the case a solution has been found because:
            // n + (target - n) == target
            const bool is_in = partial_sums.find(target - n) != partial_sums.end();
            if (is_in) {
                result_indices.push_back(i);
                result_indices.push_back(indices_map.at(target - n));
            }
            partial_sums.insert(n);
            indices_map.insert({n, i});
        }

        return result_indices;
    }
};