javascriptalgorithmtime-complexity

How to find a pair of numbers in the array which sum is closest to x with O(n) time complexity?


Given a sorted array and a number x, find a pair in that array whose sum is closest to x". How can we implement this with O(n) time complexity?

Example:

fn([10,22,28,29,30,40], 54)  // => [22, 30]

fn([1,3,4,7,10], 15)  // => [4, 10]

fn([5], 7)  // => []

fn([], 7)  // => []

Update:

It was my latest try to solve this problem, which isn't working and it has O(n^2) time complexity.

function fn(arr, x) {
  let res = [];
  if (arr.length < 2) return res;

  for (let i = 0; i < arr.length - 1; i++) {
    for (let j = arr.length - 1; j > i; j--) {
      let t = Math.abs(arr[i] + arr[j] - x);
      if (arr[i] + arr[j] === x) return (res = [arr[i], arr[j]]);
      if (arr[i] + arr[j] > x) {
        if (t > Math.abs(arr[i] + arr[j] - x)) {
          t = Math.abs(arr[i] + arr[j] - x);
          res = [arr[i], arr[j]];
        }
      }
    }
  }
  return res;
}

console.log(fn([10, 22, 28, 29, 30, 40], 54));
console.log(fn([1, 3, 4, 7, 10], 15));


Solution

  • The basic idea is very simple. To follow along from a very safe position, we will first try the farthest numbers.

    1 2 3 4 5
    ^       ^
    l       r
    

    Now we have different cases. Let's be the difference between the sum of two num and the given number is d

    At first we would allow any d. Set it a very large number.

    Then if sum of a[l]+a[r] < x then try to increase it? So it would be logical to move towards right of the sorted (ascending array) l++

    Else if it is a[l]+a[r] > x, r-- so reduce the sum or move left.

    If you are wondering why did I introduce d, maybe think a bit. But yes it is just to store the difference. So it would be absolute value of a[l]+a[r]-x.

    To be more precise, you only need to run it till you have l<r.