Efficient way to find a pair with minimum difference in an array

Question

I'm trying to solve a problem that requires me to find a pair with minimum difference in an array.

For example, if the array is

6,7,1,3,9

The output is

(6,7)

with difference of 1 which is minimum.

The fastest solution I can come up with is to sort the array and iterate through the sorted array to find the minimum difference [O(nlogn)]. Is there a way to optimise this or better solve it in O(n) or O(logn)?

Edit: All elements of the array are distinct.

Is the array always discrete and distinct? i.e. Would you ever get [1,2,3,2] or [1,2,1.5,1.56]? — Max Bilbow, Sep 24 '17 at 07:35
If so, you would at least be able to halt the iteration at the first difference of 1. That's all I've got at the moment. — Max Bilbow, Sep 24 '17 at 07:39

score 1 · Answer 1 · answered Sep 24 '17 at 07:44

Assuming all numbers are distinct and secrete, you can stop your search once the difference is 1.

There is also a wikipedia article on this problem here: https://en.wikipedia.org/wiki/Closest_pair_of_points_problem

Also another question here: Finding out the minimum difference between elements in an arrays

My improvement:

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]);
    if (minDif == 1)
        break;
}
System.out.println(minDiff);

score 1 · Answer 2 · answered Sep 24 '17 at 07:48

I wouldn't expect you can find a O(log n) solution as there is at least a need to iterate over a whole array to see its elements. For me the sorting approach seems optimal but there is a possibility to improve the O(n log n) complexity if your numbers are from a not so big set which is known before (e.g. integers from the range [0; N] for some quite small N). In such case you could use the counting sort algorithm for which the worst-case complexity is O(n + N). However, please note that the space usage is also O(n + N). There are many sources on the counting sort and this one should be sufficient: https://en.wikipedia.org/wiki/Counting_sort

score 1 · Answer 3 · answered Sep 24 '17 at 08:11

You are trying to solve the Closest Pair problem, in which you search for the two points in your dataset that have the minimum distance from each other. Setting the dimension to 1 reduces to your case (a point is just a number).

The time complexity of the algorithms solving this problem efficiently is:

O(nlogn)

Note that Divide and Conquer techniques can be used in this context. As for example in these slides.

Tip: If you assume that the data points are distinct, then you can stop your algorithm when you find a distance of 1 (since it cannot be less than 1), but this might not ever be the case for your data.

Efficient way to find a pair with minimum difference in an array

3 Answers3