Find minimum difference between any two elements

Problem: Given a unsorted array, find the pair with the minimum difference.

For example:

Input arr[] = {12, 54, 8, 12, 10}
Output: Minimum difference is 0
 
Input arr[] = {1, 5, 3, 19, 18, 25}
Output: Minimum difference is 1

Method 1: naive solution
A simple solution is to use two loops and find minimum difference pair.

#include <bits/stdc++.h>
using namespace std;

int MinDiff(int arr[], int n)
{
   /* Initialize difference as infinite */
   int diff = INT_MAX;
 
   /* Find the min diff by comparing difference
      of all possible pairs in given array */
   for (int i=0; i<n-1; i++)
   {
       for (int j=i+1; j<n; j++)
          {
              if (abs(arr[i] - arr[j]) < diff)
                diff = abs(arr[i] - arr[j]);
          }
   }
 
   /* Return min diff */
   return diff;
}

int main()
{
   int arr[] = {1, 5, 3, 19, 18, 25};
   int n = sizeof(arr)/sizeof(arr[0]);
   cout << "Minimum difference is " << MinDiff(arr, n);

   return 0;
}

Output:

Minimum difference is 1

Time complexity: O(N*N)

Method 2: Sorting the array and find the difference between consecutive elements.

#include <bits/stdc++.h>
using namespace std;
 
int MinDiff(int arr[], int n)
{
   /* Sort array in asending order */
   sort(arr, arr + n);
 
   /* Initialize difference as infinite */
   int diff = INT_MAX;
 
   /* Find the min diff by comparing adjacent
      pairs in sorted array */
   for (int i=0; i<n-1; i++)
   {
       if (arr[i+1] - arr[i] < diff)
          diff = arr[i+1] - arr[i];
   }
 
   /* Return min diff */
   return diff;
}
 
int main()
{
   int arr[] = {1, 5, 3, 19, 18, 25};
   int n = sizeof(arr)/sizeof(arr[0]);
   cout << "Minimum difference is " << MinDiff(arr, n);

   return 0;
}

Output:

Minimum difference is 1

Time Complexity: O(NlogN)