# #7 Smallest Difference

###### tags: `Array` `Medium`

## Problem
Write a function that takes in two non-empty arrays of integers, finds the pair of numbers (one from each array) whose absolute difference is closest to zero, and returns an array containing these two numbers, with the number from the first array in the first position.

Note that the absolute difference of two integers is the distance between them on the real number line. For example, the absolute difference of -5 and 5 is 10, and the absolute difference of -5 and -4 is 1.

You can assume that there will only be one pair of numbers with the smallest difference.

### Sample Input

arrayOne = [-1, 5, 10, 20, 28, 3]
arrayTwo = [26, 134, 135, 15, 17]

### Sample Output

[28, 26]

<br>

:::spoiler **Optimal Space & Time Complexity**

O(nlog(n) + mlog(m)) time | O(1) space - where n is the length of the first input array and m is the length of the second input array

:::

<br>

:::spoiler Hint 1
Instead of generating all possible pairs of numbers, try somehow only looking at pairs that you know could actually have the smallest difference. How can you accomplish this?
:::

<br>

:::spoiler Hint 2
Would it help if the two arrays were sorted? If the arrays were sorted and you were looking at a given pair of numbers, could you efficiently find the next pair of numbers to look at? What are the runtime implications of sorting the arrays?
:::

<br>

:::spoiler Hint 3
Start by sorting both arrays, as per Hint #2. Put a pointer at the beginning of both arrays and evaluate the absolute difference of the pointer-numbers. If the difference is equal to zero, then you've found the closest pair; otherwise, increment the pointer of the smaller of the two numbers to find a potentially better pair. Continue until you get a pair with a difference of zero or until one of the pointers gets out of range of its array.
Optimal Space & Time Complexity
:::

<br>

<hr/>

## Solutions

### Official

// O(nlog(n)+mlog(m)) time | 0(1) space

const getSmallestDifference = (arrayOne, arrayTwo) => {
  arrayOne.sort((a, b) => a - b);
  arrayTwo.sort((a, b) => a - b);
  let IdxOne = 0;
  let IdxTwo = 0;
  let smallest = Infinity;
  let current = Infinity;
  let smallestPair = [];
  while (IdxOne < arrayOne.length && IdxTwo < arrayTwo.length) {
    let firstNum = arrayOne[IdxOne];
    let secondNum = arrayTwo[IdxTwo];
    if (firstNum < secondNum) {
      current = secondNum - firstNum;
      IdxOne++;
    } else if (secondNum < firstNum) {
      current = firstNum - secondNum;
      IdxTwo++;
    } else {
      return [firstNum, secondNum];
    }
    if (smallest > current) {
      smallest = current;
      smallestPair = [firstNum, secondNum];
    }
  }
  return smallestPair;
};

<br>

---

### Everyone's

<h4>Tow pointers + while(two array length)：</h4>
<p>1. compare with the current pointer:</p>

:::spoiler YC

 //time: O(nlog(n) + mlog(m)) 
 //- where n is the length of the first input array and m is the length of the second input array
 //- space: O(1)
function smallestDifference(arrayOne, arrayTwo){
  arrayOne.sort((a,b) => a - b);
  arrayTwo.sort((a,b) => a - b);
  let p1 = 0, p2 = 0, min = Number.MAX_SAFE_INTEGER;
  let minP1 = 0, minP2 = 0;
  
  while(p1 < arrayOne.length && p2 < arrayTwo.length){
    const diff = Math.abs(arrayOne[p1] - arrayTwo[p2]);      
    if (diff === 0) return [arrayOne[p1],arrayTwo[p2]]
    
    if (diff < min) {
      min = Math.abs(arrayOne[p1] - arrayTwo[p2]);
      minP1 = p1;
      minP2 = p2;
    }
 
    if (arrayOne[p1] < arrayTwo[p2])
      p1++;
    else
      p2++;
  }
  
  return [arrayOne[minP1], arrayTwo[minP2]]
}

:::
:::spoiler Raiy

//Time O(nlogn) Space(2n)
function smallestDiff(arrOne, arrTwo) {
  let leftOne = 0;
  let leftTwo = 0;

  let count = null;
  let result = [];
  const sortOne = arrOne.sort((a, b) => a - b);
  const sortTwo = arrTwo.sort((a, b) => a - b);

  while (leftOne < sortOne.length && leftTwo < sortTwo.length) {
    if (count === null) {
      count = Math.abs(sortOne[leftOne] - sortTwo[leftTwo]);
    }

    if (Math.abs(sortOne[leftOne] - sortTwo[leftTwo]) < count) {
      count = Math.abs(sortOne[leftOne] - sortTwo[leftTwo]);
      result = [sortOne[leftOne], sortTwo[leftTwo]];
    }

    if (sortOne[leftOne] < sortTwo[leftTwo]) {
      leftOne++;
    } else {
      leftTwo++;
    }
  }
  return result;
}

:::
<br>

<p>2. compare with the next pointer:</p>

:::spoiler 東

//Time: O(nlogn + mlogm) Space O(1); 
//n is length of arrayOne and m is length of arrayTwo
function smallestDifference(arrayOne, arrayTwo) {
  arrayOne.sort((a, b) => a-b);
  arrayTwo.sort((a, b) => a-b);

  let idx1 = 0;
  let idx2 = 0;
  let minDiff = Math.abs(arrayOne[idx1] - arrayTwo[idx2]);
  const res = [arrayOne[idx1], arrayTwo[idx2]];
  
  while (idx1 < arrayOne.length && idx2 < arrayTwo.length) {
    const currDiff = Math.abs(arrayOne[idx1] - arrayTwo[idx2]);
    if (arrayOne[idx1 + 1] && Math.abs(arrayOne[idx1 + 1] - arrayTwo[idx2]) < currDiff) idx1 ++;
    else if (arrayTwo[idx2 + 1] && Math.abs(arrayOne[idx1] - arrayTwo[idx2 + 1]) < currDiff) idx2 ++;
    else {
      if (currDiff < minDiff){
        minDiff = currDiff;
        res[0] = arrayOne[idx1];
        res[1] = arrayTwo[idx2];
      }
      idx1 ++;
      idx2 ++;
    }
  }
  return res;
}

:::

:::spoiler SOL

const getSmallestDifference = (arrayOne, arrayTwo) => {
  arrayOne.sort((a, b) => a - b);
  arrayTwo.sort((a, b) => a - b);
  let IdxOne = 0;
  let IdxTwo = 0;
  let smallestDiff = [arrayOne[IdxOne], arrayTwo[IdxTwo]];
  while (IdxOne < arrayOne.length && IdxTwo < arrayTwo.length) {
    const [left, right] = smallestDiff;
    const difference = Math.abs(left - right);
    if (difference === 0) {
      return smallestDiff;
    }
    if (Math.abs(arrayOne[IdxOne] - arrayTwo[IdxTwo + 1]) < difference) {
      smallestDiff = [arrayOne[IdxOne], arrayTwo[IdxTwo + 1]];
      IdxTwo++;
    } else if (Math.abs(arrayOne[IdxOne + 1] - arrayTwo[IdxTwo]) < difference) {
      smallestDiff = [arrayOne[IdxOne + 1], arrayTwo[IdxTwo]];
      IdxOne++;
    } else {
      IdxOne++;
    }
  }
  return smallestDiff;
};

:::

<br>

<h4>Tow pointers + while(array one length)：</h4>
<p>reset point2</p>

:::spoiler 月

function findSmallestDistance(arr1,arr2){
  /* Time O(n*m) Space O(n) 
     n is the length of the arrayOne.
     m is the length of the arrayTwo.
  */
  let p1 = 0, p2 = 0;
  let min = [0,0,null];  // [n1,n2,difference]
  while(p1 < arrayOne.length){
    const difference = Math.abs(arrayOne[p1] - arrayTwo[p2]);
    if(difference < min[2] || min[2] === null){
      min = [arrayOne[p1], arrayTwo[p2], difference];
    }
    if(p2 === arrayTwo.length - 1){
      p1++;
      p2 = 0;
    }else{
      p2++
    }
  }
  return min.slice(0,2)
}

:::

<br>

<h4>Loop through array1, find the nearest target in array2:</h4>
use tow pointer to search the nearest target

:::spoiler Hao

const getSmallestDifference = (arrayOne, arrayTwo) => {
  /* O(nlog(m) time | O(n+m) space  */

  const arrayOneSorted = arrayOne.slice().sort((a, b) => a - b);
  const arrayTwoSorted = arrayTwo.slice().sort((a, b) => a - b);
  let diff = Infinity;
  let res = [-Infinity, Infinity];

  const getTargetSmallestDifferenceInfo = (target, arr) => {
    let pointerLeft = 0;
    let pointerRight = arr.length - 1; // 3

    while (pointerRight - pointerLeft !== 1 && pointerRight > pointerLeft) {
      let pointerMid = pointerLeft + Math.ceil((pointerRight - pointerLeft) / 2); // 2
      if (arr[pointerMid] > target) pointerRight = pointerMid;
      else pointerLeft = pointerMid;
    }

    if (Math.abs(target - arr[pointerLeft]) > Math.abs(target - arr[pointerRight])) return [Math.abs(target - arr[pointerRight]), arr[pointerRight]];
    else return [Math.abs(target - arr[pointerLeft]), arr[pointerLeft]];
  };
  arrayOneSorted.forEach((valueOne) => {
    const [currentSmallestDiff, valueTwo] = getTargetSmallestDifferenceInfo(valueOne, arrayTwoSorted);
    if (currentSmallestDiff < diff) {
      diff = currentSmallestDiff;
      res = [valueOne, valueTwo]
    };
  });

  return res;
};

:::

<br>

<h4>2 for loop:</h4>

:::spoiler Becky

//time: O(n^2) | space: O(1)
function smallestDifference(arr1, arr2){
  let result = Number.MAX_SAFE_INTEGER;
  let ans = [];
  for(let i = 0; i < arr1.length; i++){
    for(let j = 0; j < arr2.length; j++){
      if(Math.abs(arr1[i] - arr2[j]) < result){
        result = Math.abs(arr1[i] - arr2[j]);
        ans = [arr1[i],arr2[j]];
      }
    }    
  }
  return ans;
}

:::

<br>

---

## Supplement / Discussion

#### 可以表示最大值的方式：
* Infinity(沒有人比他大)
* Number.MAX_VALUE (1.7976931348623157e+308)
* Number.MAX_SAFE_INTEGER (9007199254740991)

#### 可以獲取到兩個數字實際差距的方式：

* 大數減小數
* Math.abs() 取決對值

#### 空間複雜度：會不會因為input的大小而影響需要使用的記憶體容量