Minimum Absolute Difference

mad.js

// Minimum Absolute Difference in an Array
// comparing each pair O(n^2)
// sort first O(nlogn) + O(n)
exports.mad = function(arr) {
  const a = arr.sort((a, b) => a - b);
  let min = -1;

  for (let i = 0, l = a.length; i < l - 1; i++) {
    const d = Math.abs(a[i] - a[i + 1]);
    if (min < 0 || d < min) {
      min = d;
    }
  }

  return min;
};

// Find mad between two arrays
// sort first otherwise O(n^2)
// Find Minimum aboslute difference between two sorted arrays
// Given two arrays sorted in ascending order, find the absolute minimum difference between any pair of elements |a-b| such that a is from one array and b is from another array.
// O(n)
// what is returning all the pairs?
exports.mad2 = function(a1, a2) {
  let i = 0,
    j = 0,
    r = -1;

  while (i < a1.length && j < a2.length) {
    const d = Math.abs(a1[i] - a2[j]);
    if (d === 0) return 0;

    if (r < 0 || d < r) {
      r = d;
    }

    if (a1[i] < a2[j]) {
      i++;
    } else {
      j++;
    }
  }

  return r;
};

// Find mad between three arrays
// O(n^3) brute force
// min{|a-b| + |b-c| + |a-c|} a, b, c from three sorted arrays
// min{|max(a,b,c) - min(a,b,c)|} * 2
exports.mad3 = function(a1, a2, a3) {
  let i = 0,
    j = 0,
    k = 0,
    r = -1;

  while (i < a1.length && j < a2.length && k < a3.length) {
    const max = Math.max(a1[i], a2[j], a3[k]);
    const min = Math.min(a1[i], a2[j], a3[k]);
    const d = Math.abs(max - min);
    if (d === 0) return 0;

    if (r < 0 || d < r) {
      r = d;
    }

    if (min === a1[i]) {
      i++;
    } else if (min === a2[j]) {
      j++;
    } else if (min === a3[k]) {
      k++;
    }
  }
  return r * 2;
};

test.js

const { mad, mad2, mad3 } = require('./mad');

test('mad', () => {
  expect(mad([-2, 2, 4])).toEqual(2);
  expect(mad([-59, -36, -13, 1, -53, -92, -2, -96, -54, 75])).toEqual(1);
  expect(mad([1, -3, 71, 68, 17])).toEqual(3);
});

test('mad2', () => {
  expect(mad2([1, 2, 3], [7, 8, 9])).toEqual(4);
});

test('mad3', () => {
  expect(mad3([2, 5, 8], [7, 10, 12], [6, 9, 14])).toEqual(4); // 8, 7, 6
  expect(mad3([9, 12, 15, 18], [8, 10, 13, 17], [5, 11, 14, 16])).toEqual(4); // 11, 10, 9
});