# Accepted C++ O(n) solution via counting_sort

• ``````#include <vector>
#include <algorithm>

using namespace std;

void counting_sort(vector<int>& numbers)
{

vector<int> p_pos_vec(100000, 0);     // For positive numbers
vector<int> n_pos_vec(100000, 0);    // For negative numbers
vector<int> sorted_vec(numbers);

for (vector<int>::iterator iter = numbers.begin();
iter != numbers.end(); ++iter)
{
if (*iter >= 0)
++p_pos_vec[*iter];
else
++n_pos_vec[-*iter];
}

for (vector<int>::iterator _b_iter = n_pos_vec.end() - 2;
_b_iter >= n_pos_vec.begin(); --_b_iter)
{
*_b_iter += *(_b_iter + 1);
}

*p_pos_vec.begin() += *n_pos_vec.begin();

for (vector<int>::iterator iter = ++p_pos_vec.begin();
iter != p_pos_vec.end(); ++iter)
{
*iter += *(iter - 1);
}

for (vector<int>::iterator b_iter = --numbers.end();
b_iter >= numbers.begin(); --b_iter)
{
if (*b_iter >= 0)
sorted_vec[--p_pos_vec[*b_iter]] = *b_iter;
else
sorted_vec[--n_pos_vec[-*b_iter]] = *b_iter;
}

copy(sorted_vec.begin(), sorted_vec.end(), numbers.begin());
}

class Solution {
public:
vector<int> twoSum(vector<int> &numbers, int target) {

vector<int> result;
vector<int> sorted_vec(numbers);
counting_sort(sorted_vec);

// Give two pointers, one moves forward and another one
// moves backward
vector<int>::iterator f_iter = sorted_vec.begin();
vector<int>::iterator b_iter = --sorted_vec.end();

while (f_iter != b_iter)
{
int sum = *f_iter + *b_iter;

if (sum == target)
{
// Find the two values from the vector
for (vector<int>::iterator f_i = numbers.begin();
f_i != numbers.end(); f_i++) {
if (*f_i == *f_iter) {
f_iter = f_i;
break;
}
}

for (vector<int>::iterator b_i = --numbers.end();
b_i >= numbers.begin(); b_i--) {
if (*b_i == *b_iter) {
b_iter = b_i;
break;
}
}

result.push_back(min(f_iter, b_iter) - numbers.begin() + 1);
result.push_back(max(f_iter, b_iter) - numbers.begin() + 1);
return result;
}

if (sum < target) f_iter++;

if (sum > target) b_iter--;
}

return result;
}
};``````

• Pay attention to "Writing code? Select all code block then click on the {} button to preserve code formatting.” above text editor.

• Thanks a lot, this is what I need.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.