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

Question

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;
                 }
             }
         }

Answer 1

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.

Answer 2

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.