find ordered pairs is array with given sum but array has duplicate values

I want to solve the problem: find all ordered pairs in an array where
A[i] + A[j] = q , i != j

for example: array = [1,3,3,3] q = 6
output = [[3,3], [3,3], [3,3], [3,3], [3,3], [3,3]]

I can't use any other data-structure
in O(N) time (not including sort time) and O(1) space.

I have been able to come up with a algorithm for array with unique elements though! here is the code:

function findTuples(arr: number[], q: number): Array<[number, number]> {
    // Sort the array in ascending order
    arr.sort((a, b) => a - b);

    let low = 0;
    let high = arr.length - 1;
    let result: Array<[number, number]> = [];

    // While low pointer is less than high pointer
    while (low < high) {
        let sum = arr[low] + arr[high];

        // If sum of two elements is equal to q
        if (sum === q) {
            result.push([arr[low], arr[high]]);
            result.push([arr[high], arr[low]]);

            low++;
            high--;
        } else if (sum < q) {
            // If sum is less than q, move low pointer up
            low++;
        } else {
            // If sum is greater than q, move high pointer down
            high--;
        }
    }

    return result;
}

I am trying to solve this using two pointers method but I can't come up with the right algorithm.

is it even possible?!

The number of pairs to output could be in the order of O(n²). It is not possible to design an algorithm with time complexity O(n) that can produce output with size O(n²). And O(1) space complexity isn't possible for the same reasons, unless we exclude the space used for the output.

However, the O(n²) sized output could be reduced to O(n) if we allow the output to list a distinct pair only once, but with an indication how many occurrences there would be for it. For your example this would mean we could produce this output:

[ [[3,3], 6] ]

...meaning that [3,3] is a solution that has 6 occurrences. If we allow for that (compressed) output format, then it is possible to have a time complexity of O(n).

We could use the 2 pointer algorithm for this, but here I will use a hashmap (Map) instead, assuming that it has an (amortised) time complexity of O(1) for get and set operations. The advantage is that the input does not have to be sorted for this to work:

<!-- begin snippet: js hide: false console: true babel: false -->

<!-- language: lang-js -->

function findTuples(arr, q) {
    const count = new Map;
    const result = [];
    // Collect the frequency for each distinct value
    for (const value of arr) {
        count.set(value, (count.get(value) ?? 0) + 1);
    }

    for (const [a, countA] of count) {
        // Get the complementary value needed to arrive at the sum
        const b = q - a;
        if (a === b) { // Special case
            result.push([[a, a], countA * (countA - 1)]);
        } else { // All other cases
            const countB = count.get(b);
            if (countB) {
                result.push([[a, b], countA * countB]);
            }
        }
    }
    return result;
}

// The example input from the question
const result = findTuples([1,3,3,3], 6);
console.log(result);

// Another input:
const result2 = findTuples([1,2,2,4,4], 6);
console.log(result2);

<!-- end snippet -->

The word "ordered" is a little vague, but if there really is an O(n) solution then the goal must be to step through the array starting at 1 and add that value to the previous value and perform the comparison. If it succeeds, then that pair is added to the list, and the index is incremented.

function findTuples(arr, q) {
  let result = [];
  for (let i = 1; i < arr.length; i++) {
    if (arr[i - 1] + arr[i] === q)
      result.push([arr[i - 1], arr[i]]);
  }
  return result;
}

However the problem requirement is not clear. If it's required to find all pairs of values from the start array, like combinations of 2 values taken from anywhere in the array, then that won't be linear. So in that case the O(n) requirement does not make sense.

Oh, also, and this is probably debatable, but because the output is a new lot of storage (at least in JavaScript), I'm not sure you could call this O(1) in terms of space used.

Use two pointers. Set the left pointer to index 0. Use binary search to place the right pointer, finding the largest index associated with a value such that arr[left] + arr[right] <= target.

Maintain your output, either a list of pairs of indices, or a count.

Repeatedly do the following:

if arr[left] != arr[right]
  if arr[left] + arr[right] < target
    increment left
  else if arr[left] + arr[right] > target
    decrement right
  else # arr[left] + arr[right] == target
    count the number of identical elts to arr[left] and arr[right]. 
    Call these left_count and right_count. At a minimum these are both 1.
    Increment count by left_count * right_count or update the list of pairs of indices for all such pairs. 
    Finally, increment left and decrement right so both associated values change (i.e. each increments per number of identical values).
else
  if arr[left] + arr[right] == target
    count += choose(right - left + 1, 2) # or update the list of pairs of indices to reflect all pairs of 2 indices between left & right inclusive
  return

Stop when left == right or if we reach the return statement.

Example: [1, 1, 1, 2, 2] for target 3: We start with left=0 and right=4. We're in the final else of the first if, since arr[left] + arr[right] == target. Since left_count = 3 and right_count = 2, we've found 3*2 = 6 new pairs that meet our target, after which we're done. If we're building the list of pairs, it's each of [0,1,2] paired with each of [3,4].

Example: 1, 2, 2, 2, 3 for target 4: We again start with left=0 and right=4, again in the final else of the first iff. Here left_count = right_count = 1, so we increment count by 1 (or add (0,4) to our list) and now left=1 and right=3. Now we're in the final else statement, so add choose(3,2) or every pair of 2 indices from [1,2,3] to our list.

Using two points, when you find arr[left] + arr[right] == q, move left and right to find out how many same number equals arr[left] and arr[right], then put the pair in result.

public List<int[]> findTuples(int[] arr, int q)
{
List<int[]> result = new LinkedList<int[]>();
int left = 0;
int right = arr.length - 1;
int tempLeft;
int tempRight;
while(left <= right && left < arr.length && right >= 0)
{
if (arr[left] + arr[right] < q)
{
left++;
}
else if (arr[left] + arr[right] > q)
{
right--;
}
else
{
tempLeft = left;
tempRight = right;
//if [left, right] is all same numbers
if (arr[left] == arr[right])
{
int count = (tempRight- tempLeft + 1)*(tempRight - tempLeft);
for (int i = 0; i < count; i++)
{
result.add(new int[]{arr[tempLeft], arr[tempRight]});
}
break;
}
else
{
//find same number in left and right side
while(left < arr.length && arr[left] == arr[tempLeft]) 
{
left++;
}
while(right >= 0 && arr[right] == arr[tempRight])
{
right--;
}
//add the pairs into result
for (int i = 0; i < left - tempLeft; i++)
{
for (int j = 0; j < tempRight - right; j++)
{
result.add(new int[]{arr[tempLeft], arr[tempRight]});
result.add(new int[]{arr[tempRight], arr[tempLeft]});
}
}
}
}
}
return result;
}

thanks for all the answers! really valuable!
here is the solution I came up with

function findOrderedPairs(arr: number[], sum: number) {
const result: number [][] = [];
arr.sort((a ,b) => a - b);
let low = 0, high = arr.length - 1;
while (low < high) {
if (arr[low] + arr[high] < sum) {
low++;
} else if (arr[low] + arr[high] > sum) {
high--;
} else {
result.push([arr[low], arr[high]]);
result.push([arr[high], arr[low]]);
let runner = low + 1;
while (runner < high && arr[runner] === arr[low]) {
result.push([arr[runner], arr[high]]);
result.push([arr[high], arr[runner]]);
runner++;
}
high--;
}
}
return result;
}
console.log(findOrderedPairs([1, 3, 3, 3], 6));
// output: [ [ 3, 3 ], [ 3, 3 ], [ 3, 3 ], [ 3, 3 ], [ 3, 3 ], [ 3, 3 ] ]
</details>