averagePair problem using multiple pointers as a solution

Question

I'm trying to solve the following problem :

What I've come up with so far:

function averagePair(arr,tar){

    if (arr.length < 2){
        return false
    }

    let x = 0

    for (var y = 1; y < arr.length; y++){
        if ((arr[x] + arr[y]) / 2 == tar){
            return true
        }
        else {
            x++;
        }
    }
    return false
}

I know this solution isn't correct, can someone explain why? It works for some cases but not all

CertainPerformance · Answer 1 · 2020-10-19T23:24:11.930

You're only comparing adjacent elements, eg [0] vs [1], and [1] vs [2]. You also need to compare [0] vs [2] and so on. The simplest tweak would be to use a nested loop:

for (let x = 0; x < arr.length; x++) {
  for (let y = 0; y < arr.length; y++) {
    if (x !== y) {
      // test arr[x] against arr[y]

But it'd be more elegant and less computationally complex (O(n) instead of O(n ^ 2)) to use a Set to keep track of what's been found so far:

const nums = new Set();
for (const num of arr) {
  if (nums.has(tar - num)) {
    return true;
  } else {
    nums.add(num);
  }
}

function averagePair(arr,tar){
  const nums = new Set();
  for (const num of arr) {
    if (nums.has(tar - num)) {
      return true;
    } else {
      nums.add(num);
    }
  }
  return false;
}

console.log(averagePair([-2, 3, 2], 0));
console.log(averagePair([-2, 3, 3], 0));

I see - any ideas how to go about it without a nested loop. The question requires O(N) time complexity — st123, Oct 19 '20 at 23:08

fas · Accepted Answer · 2020-10-20T00:57:08.167

There's a solution with O(1) additional space complexity and O(n) time complexity.

Since an array is sorted, it makes sense to have two indices: one going from begin to end (say y), another from end to begin of an array (say x).

Here's the code:

function averagePair(arr,tar){
    
    // That's now included in for-loop condition
    // if (arr.length < 2) {
    //     return false;
    // }

    let x = arr.length - 1;

    for (var y = 0; y < x; y++) {

        // Division may lose precision, so it's better to compare
        //   arr[x] + arr[y] > 2*tar
        // than
        //   (arr[x] + arr[y]) / 2 > tar

        while (y < x && arr[x] + arr[y] > 2*tar) {
            x--;
        }
        if (x != y && arr[x] + arr[y] == 2*tar) {
            return true;
        }
    }
    return false;
}

It's kinda two-pointers technique: we'll decrease x until a[x] + a[y] > 2*tar for current loop iteration because we need to find the closest match. At the next for-loop iteration a[y] is greater or equal than the previous one, so it makes no sense to check if a[z] + a[y] == 2*tar for any z > x. We'll do this until indices aren't equal, which means there's no match.

thanks for the explanation! what exactly do you mean that division will lose precision? — st123, Oct 20 '20 at 03:59
@sofiat123 in this particular case division by two shouldn't cause any problems, but generally if you can it's better to avoid floating point calculations (see [this](https://stackoverflow.com/questions/588004/is-floating-point-math-broken) for example) — fas, Oct 20 '20 at 04:26

averagePair problem using multiple pointers as a solution

2 Answers2