# Finding all pairs of elements in an array that sum to a target value using multiple pointers

I was thinking about this problem where you should make a function that takes an array and a target value and then it will find all the pair values that sums up to that target value.

Of course there is the naive way using nested loops, but I want to avoid the O(n²) time complexity so I have came up with this solution.

Knowing that

• Array is sorted.
• Length is static (for the testing purpose only)

### Particular concerns

• does it scale better than O(n²)?

• could I do better?

#include <vector>
using namespace std;

void pairs_sum_up_to_value(int arr[], int target)
{
int p1 = 0;
int p2 = 15;
int flag = 2;

vector<result> res;
while (p1 < p2)
{
if (arr[p1] + arr[p2] == target)
{

for (int k = 0; k < res.size() - 1; k++)
{
if (res.size() == 0)
res.push_back(result(arr[p1], arr[p2]));
else if (res[k].num1 != arr[p1] && res[k].num2 != arr[p2])
{
flag = 1;
}
else flag = 0;
}
if(flag == 0) res.push_back(result(arr[p1], arr[p2]));
p1++;
}
else if (arr[p1] + arr[p2] < target)
{
p1++;
continue;
}
else if (arr[p1] + arr[p2] > target)
{
p2--;
for (int i = p1; i >=0; i--)
{
if (arr[i] + arr[p2] == target)
{
res.push_back(result(arr[p1], arr[p2]));
}
else if (arr[i] + arr[p2] > target)
{
continue;
}
else break;
}
}
}
• You're missing a definition of vector - is that supposed to be std::vector? Commented Apr 30, 2021 at 8:07
• No, I have used the std namespace to shorten the code.
– PixD
Commented May 2, 2021 at 23:05
• Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. Please see what you may and may not do after receiving answers. Commented May 3, 2021 at 0:36

This is a typical LeetCode problem. I would write an O(n) solution as follows:

#include <unordered_set>
#include <utility>
#include <vector>

template <typename T>
std::vector<std::pair<T, T>> twoSum(const std::vector<T>& arr, const T& target) {
std::unordered_set<T> seen;
std::vector<std::pair<T, T>> result;
for (const auto& num : arr) {
T complement = target - num;
if (seen.contains(complement)) {
result.emplace_back(num, complement);
}
seen.insert(num);
}
return result;
}

Now let's review your solution:

• Don't hardcode array length. int p2 = 15; Don't do this. You can't assume that the length of input array is always 16.

• Don't use struct result. Instead, use pair<int, int>

• The solution is wrong, you can't use two pointers in this case without sorting.

• You should insert the solution when flag = 1, not 0.

• If the arr values are not unique, you might insert duplicates. It makes sense that a solution of {4,4} is only admitted if there are at least two 4's present, and your code (seen.insert called after checking) will accommodate that. But do you want all pairs of input to be included (like when evaluating Cribbage hand scores, for example) or only one copy of each pair of values? You're doing neither, and the use of the set would not count all possible pairs. Commented Apr 30, 2021 at 14:42
• @JDługosz Sure, then we can switch to std::unordered_map<T, std::size_t> and return the pair of indices. Commented Apr 30, 2021 at 14:44
• I am sorry that the question is not clear, but in this solution we assume that the array is already sorted and because it was only a test in my free time, I used a static array, of course that should not be done in normal cases. - I didn't know about the pair DT, it was an addition for me so, thanks!
– PixD
Commented May 2, 2021 at 23:01
void pairs_sum_up_to_value(int arr[], int target)

What's the length of arr? You should make it work like an STL algorithm, so it takes two iterators, or a range of some kind.

There's no return value? Where does the result go?? I see you have a result vector inside the function, but it's not returned.

int p1 = 0;
int p2 = 15;
int flag = 2;

Despite your naming of p_ and the text that you give before the code, these are not pointers. They are indexes.

Using actual pointers (or more generally, iterators) would be more normal. The begin and end points would be the parameters to the function.

What is flag? I see it starts out as 2, might be set to 0 or 1, but there's no clue as to what it means. The only code that reads flag cares if it's 0, so why do you have 1 and 2 distinguished? It might be properly a bool called something that indicates its meaning.

As for the meaning, it is whatever the last iteration of the preceding loop left it as. So there's no reason to loop at all; just look at the last element since that's the only thing that has any effect. Otherwise I think it resembles a search of some kind, but of course it's not. Hmm, does this code actually work? If not, this question should be closed since we only review correct working code. I'm not sure how you even know if it works or not, since the result you computed is not returned or printed out or anything.

• It's working of course, if it's not I would have posted it on Stack Overflow. - I was only testing the solution, so I didn't put the size in mind because I was testing it on a static array, but if it was to be implemented in a program, I would put additional parameter for the length. - there is no return value for the same reason also, I printed all the values stored in the result's vector and it's actually working.
– PixD
Commented May 2, 2021 at 22:43
• - I didn't use pointers because I thought it's not necessary since I don't need to do something with the address of the values, I only want to know the values in the array that sum up to the target value. - I used the flag for the searching algorithm that I used, which is if the pair of the values which is recently found is already in the vector, flag value will be 1 instead of 0, and I push values depending on the value of the flag, but I see that it should be a bool, I didn't see that when I was coding it. - Sorry, I didn't get the last point, can you clarify it more for me?
– PixD
Commented May 2, 2021 at 22:56
• There's no print statements in the code you posted. So I see code that does the work and then throws it away. Commented May 3, 2021 at 14:12