Finding out the minimum difference between elements in an array

The minimum difference will be one of the differences from among the consecutive pairs in sorted order. Sort the array, and go through the pairs of adjacent numbers looking for the smallest difference:

int[] a = new int[] {4, 9, 1, 32, 13};
Arrays.sort(a);
int minDiff = a[1]-a[0];
for (int i = 2 ; i != a.length ; i++) {
    minDiff = Math.min(minDiff, a[i]-a[i-1]);
}
System.out.println(minDiff);

This prints 3.

While all the answers are correct, I wanted to show the underlying algorithm responsible for n log n run time. The divide and conquer way of finding the minimum distance between the two points or finding the closest points in a 1-D plane.

The general algorithm:

• Let m = median(S).
• Divide S into S1, S2 at m.
• δ1 = Closest-Pair(S1).
• δ2 = Closest-Pair(S2).
• δ12 is minimum distance across the cut.
• Return δ = min(δ1, δ2, δ12).

Here is a sample I created in Javascript:

// Points in 1-D
var points = [4, 9, 1, 32, 13];

var smallestDiff;

function mergeSort(arr) {
  if (arr.length == 1)
    return arr;

  if (arr.length > 1) {
    let breakpoint = Math.ceil((arr.length / 2));
    // Left list starts with 0, breakpoint-1
    let leftList = arr.slice(0, breakpoint);
    // Right list starts with breakpoint, length-1
    let rightList = arr.slice(breakpoint, arr.length);

    // Make a recursive call
    leftList = mergeSort(leftList);
    rightList = mergeSort(rightList);

    var a = merge(leftList, rightList);
    return a;
  }
}

function merge(leftList, rightList) {
  let result = [];
  while (leftList.length && rightList.length) {
    // Sorting the x coordinates
    if (leftList[0] <= rightList[0]) {
      result.push(leftList.shift());
    } else {
      result.push(rightList.shift());
    }
  }

  while (leftList.length)
    result.push(leftList.shift());

  while (rightList.length)
    result.push(rightList.shift());

  let diff;
  if (result.length > 1) {
    diff = result[1] - result[0];
  } else {
    diff = result[0];
  }

  if (smallestDiff) {
    if (diff < smallestDiff)
      smallestDiff = diff;
  } else {
    smallestDiff = diff;
  }
  return result;
}

mergeSort(points);

console.log(`Smallest difference: ${smallestDiff}`);

You can take advantage of the fact that you are considering integers to make a linear algorithm:

1. First pass: compute the maximum and the minimum
2. Second pass: allocate a boolean array of length (max - min + 1), false initialized, and change the (value - min)th value to true for every value in the array
3. Third pass: compute the differences between the indexes of the true valued entries of the boolean array.

I would put them in a heap in O(nlogn) then pop one by one and get the minimum difference between every element that I pop. Finally I would have the minimum difference. However, there might be a better solution.