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));
```

·
Juan Pablo Isaza

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`

.

·
Juan Pablo Isaza
Report

I solved it in javascript code:

```
function fn(arr, x) {
let res = [];
if (arr.length < 2) return res;
let i = 0,
j = arr.length - 1,
t = Math.abs(arr[i] + arr[j] - x);
while (i < j) {
let s = arr[i] + arr[j];
if (s === t) {
res = [arr[i], arr[j]];
break;
}
if (s < x) {
i++;
if (Math.abs(arr[i] + arr[j] - x) < t) {
t = Math.abs(arr[i] + arr[j] - x);
res = [arr[i], arr[j]];
}
}
if (s > x) {
j--;
if (Math.abs(arr[i] + arr[j] - x) < t) {
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));
console.log(fn([5], 7));
console.log(fn([], 7));
```

·
Juan Pablo Isaza
Report