Sorting: Find minimum difference between any two elements in a array

Problem Statement:

Given an unsorted array, find the minimum difference between any pair in the given array

Example:

Input: [1, 4, 8, 6, 11, 10]

Output: 1

Minimum difference between 10 - 11 is 1

Solution 1:

Create 2 nested loops and generate every pair of elements and compare them to get the minimum difference.

Time Complexity: O(n*n)
Space Complexity: O(1)

Solution 2: Sorting

Sort the array

Compare all adjacent pairs in the sorted array and keep track of the min difference

Time Complexity: O(n logn)
Space Complexity: O(1)

Code Solution

#include <iostream>
#include <vector>
#include <unordered_set>
#include <algorithm>
#include <limits.h>

using namespace std;

int solution_1(int arr[], int n) 
{ 
    int diff = INT_MAX; 
  
    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 diff; 
} 

int solution_2(int arr[], int n) 
{ 
    sort(arr, arr + n); 
  
    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; 
} 
  
int main() 
{ 
    int arr[] = {1, 4, 8, 6, 11, 10 }; 
    int n = sizeof(arr) / sizeof(arr[0]); 
  
    cout << "Minimum difference is " << solution_1(arr, n); 
    cout << "\nMinimum difference is " << solution_2(arr, n); 
    return 0; 
}

Output

Minimum difference is 1
Minimum difference is 1