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

Question

The previous question was not clear enough so I will try to clarify it more in this follow-up question.
I tried the multiple pointers technique to solve the problem that find pair of values that sums up to a target value.

We are assuming that:

• the array is already sorted.
• we are working with a static array of size 16 (testing purpose only).
• we are not working with actual pointers; because we don't need them in this case (I think), I named the question on the algorithm's name only.

#include <iostream> 
#include <vector> 
using namespace std;

struct result
 {
     int num1;
     int num2;
     result() {}

     result(int num1, int num2)
         : num1{ num1 }, num2{ num2 } {}
 };

 vector<result> mult_pt(int arr[], int target)
 {
     int p1 = 0;
     int p2 = 15;
     bool flag = false;
     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 = false;
                 }
                 else flag = true;
             }
             if(flag) 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;
             }
         }
     }
     return res;
 }

int main ()
{
  int array[16] = { 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
  vector <result> res = mult_pt(array, 19);
  for (int j = 0; j < res.size(); j++)
    {
        cout << "[ " << res[j].num1 << " , " << res[j].num2 << " ]" << endl;
    }
  return 0;
}

The output should be like:

[ 4 , 15 ]
[ 5 , 14 ]
[ 6 , 13 ]
[ 7 , 12 ]
[ 8 , 11 ]
[ 9 , 10 ]
[ 10 , 9 ]

You can check the previous post here.

Answer 1

using namespace std;

There are lot of good answers why you shouldn't use it. See here

---

Use std::pair<int, int>

Since your result struct is just acting as a container for two ints, consider using std::pair<int, int>

---

Don't hardcode values

Why do you want hardcode 16 as the array length? You can just pass it to the function as a parameter, or use std::array. Your code should be able to handle any number of elements.

---

while(p1 <= p2)

This is incorrect. This will allow the algorithm to run for single length arrays as well. For example, consider the array {7} and target value 14. Your code returns {7,7} as an answer. In fact, the rogue [10, 9] in your output is a direct result of this.

---

Comparison of signed and unsigned ints

If you turn on warnings -Wall -pedantic, you will see your compiler warn you about comparing signed and unsigned ints. For example, comparing k which is a signed int to res.size() - 1 which is an unsigned int.

In fact, you're quite lucky that the first time you encounter a valid pair, it's inserted into the result vector. res.size() - 1 wraps around to whatever the maximum value of vector<result>::size_type is (in my case, 18446744073709551615) which means k < res.size() - 1 is valid.

In fact, you don't even need this entire loop (see below).

Use curly braces consistently

Your use of curly braces is very inconsistent. As a general use, always use curly braces for your conditional statements. It looks cleaner and can help avoid subtle bugs.

---

Since you're using arr[p1] + arr[p2] quite a bit, better to use a variable to store the value.

---

if(res.size() == 0) is irrelevant because it's always gonna be false (ignoring that one case at the very beginning because it's poor code, not an edge case to be handled).

---

I'm still not quite sure what the flag variable is mean to do. All your inner loop is doing is looking at the second to last element in the res vector and comparing values. flag will never be true unless the second to last element in the res vector has elements matching arr[p1] and arr[p2].

---

You have needlessly complicated your algorithm (the inner loop inside of the else if block, for example).

In pseudocode, this algorithm can be written as:

while(p1 < p2)
      sum = array[p1] + array[p2]
      if sum == target
           insert into res vector
           p1++
           p2--
     else if sum < target
           p1++
    else
           p2--

---

You could use res.emplace_back(arr[p1], arr[p2]); instead of res.push_back(result(arr[p1], arr[p2]));. The former constructs the struct in-place, while the latter might invoke the move constructor.