Question 199211 in Javascript Question posted in
A very good W3school tutorial can be found here.

Javascript – 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?!

Tags:

2

Answers


  1. 0

    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.

    Login or Signup to reply.
  2. 0

    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
    increment count or update list of pairs of indices
  if arr[right-1] == arr[right]
    decrement right
  else
    increment left
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.

    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search