wangzuo · October 16, 2018 07:26 · Oct 16, 2018
diff --git a/mad.js b/mad.js
@@ -0,0 +1,76 @@
+// 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;
+};
diff --git a/test.js b/test.js
@@ -0,0 +1,16 @@
+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
+});