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

# 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 pseudo code 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 arrray 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; } };