Smallest Difference

Given two arrays of integers, find the pair of values (one value in each array) with the smallest (non-negative) difference.

Sorting Solution

  1. Sort both the arrays in ascending order. Note: This will take O(nlogn) complexity.
  2. Declare a variable called smallest and initialize it to Infinity or Math.Max.
  3. Declare another variable called current and initialize it to Infinity or Math.Max. This will keep track of the running difference which we can later compare with smallest and determine which is the smallest difference so far.
  4. Declare two pointers, i and j which will iterate over arr1 and arr2 respectively. Also declare an array called smallestPair which will keep track of the smallest difference pair.
  5. Run a while loop till the lengths of the two arrays.
  6. Let firstNum = arr[i] and secondNum = [arr[j]. Check which one is greater. If firstNum < secondNum, Update the current to be secondNum - firstNum and increment i value. We increment the i value because since the array is sorted, we will get a higher number if we increment i and ultimately there's a chance of a smaller difference coming up.
  7. Otherwise, if firstNum > secondNum, increment j and set current equal to firstNum - secondNum.
  8. Third case is if firstNum === secondNum. In this case, the difference is zero and that will be our answer.
  9. Lastly, compare current and smallest. If current < smallest, set current = smallest and smallestPair will be arr[i], arr[j].

Time complexity

  • O(nlogn) because we sort the arrays.
Solve Smallest Difference on Algochurn

Practice all the solutions below

Practice the most popular front-end questions asked in coding interviews with   Frontend Churn