Find minimum difference between any two elements

Given an unsorted array, find the minimum difference between any pair in given array.^[1]

Pick up any non duplicated element from an array.

Input: arr[] = [1,5,3,19,18,25]
Output: 1
Minimum difference is between 18 and 19

Brute Force

int findMinimum(vector<int> &v) {
	int size = v.size();
	int min{INT_MAX};
	int diff{0};
	for (int i = 0; i < size - 1; i++) {
		for (int j = i + 1; j < size; j++) {
			diff = abc(v[i] - v[j]);
			if (diff < min) {
				min = diff;
			}
		}
	}
	return min;
}

Analysis

It picks up one of the element and compare the rest of elements. We need to use a nested loop to iterate through all of the elements.

Time complexity is $O(N^2)$ which is not as a good idea.

It doesn't use any extra space, so the space complexity is $O(1)$.

Optimized Method

1. Sort array in ascending order. This step takes $O(nLogn)$.
2. Initialize difference as infinite. This step takes $O(1)$.
3. Compare all adjacent pairs in sorted array and keep track of minimum difference. This step takes $O(n)$.

int N = arr.size();
sort(arr, arr+(N-1));
int diff = INT_MAX;
for (int i = 0; i < (N-1); i++) {
	if (arr[i+1] - arr[i] < diff) diff = arr[i+1] - arr[i];
}
return diff;

Analysis