Find minimum difference between any two elements

Problem Statement

You are given an array of integers. The problem statement asks to find minimum difference between any two elements given in the array.

Example

arr[] = {11,1,6,8,20,13}

2

Explanation: Minimum difference between 11 and 13 is 2.

arr[] = {19,14,80,200,32,29}

3

Explanation: Minimum difference between 32 and 29 is 3.

Algorithm to find minimum difference between any two elements

1. Sort the array.
2. Set the output to the maximum value of an integer.
3. Check the minimum difference of adjacent pairs and get the minimum difference into the output.
4. Return output.

ExplanationE

We have given an integer array. We need to find minimum difference between any two elements. For this we are going to sort the array first, we need to sort the array in ascending order. This is because we are going to traverse and we will be checking each of the pairs with them and their difference. Sorting takes O (n log n) time and thus can be considered as efficient.

Let us take an example with us.

Arr[] = {11,1,6,8,20,13}, we will be sorting it. After sorting the array, we have the array as {1, 6, 8, 11, 13, 20}. We are going to set the value of output to the maximum value an integer can hold. This is because we are going to find the minimum value and for this, we have to compare with the minimum elements and if have we don’t have any greater number, we can’t compare and also we won’t be able to find out the minimum value because that initial minimum value which we had chosen will become the answer. Even though that value may or may not occur while our calculation.

So we are now going to get the difference of each adjacent pair now. Starting from the first if we take the 1 and 6 we have 5 as a minimum difference, between 6 and 8 we have 2 as a minimum difference, 8 and 11 we have 3 so we will not be considering it we already have 2 as a difference which is minimum than 3. With 11 and 13 we have a minimum difference of 2 and with 13 and 20 we have 7 as a difference but 7 is also bigger than our current minimum difference which is 2. So we will be picking up 2 as our output and return it. So, this is how we find minimum difference between any two elements.

Implementation in C++ for find minimum difference between any two elements

#include<bits/stdc++.h>
#include<algorithm>

using namespace std;

int getMinimumDif(int arr[], int n)
{
    sort(arr, arr+n);

    int output = INT_MAX;

    for (int i=0; i<n-1; i++)
        if (arr[i+1] - arr[i] < output)
            output = arr[i+1] - arr[i];

    return output;
}
int main()
{
    int arr[] = {11,1,6,8,20,13};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << "Minimum difference: " << getMinimumDif(arr, n);
    return 0;
}

Minimum difference: 2

Implementation in Java for find minimum difference between any two elements

import java.util.Arrays;

class minimumDiffPair
{
    static int getMinimumDif(int[] arr, int n)
    {
        Arrays.sort(arr);

        int output = Integer.MAX_VALUE;

        for (int i=0; i<n-1; i++)
            if (arr[i+1] - arr[i] < output)
                output = arr[i+1] - arr[i];

        return output;
    }
    public static void main(String[] args)
    {
        int arr[] = {11,1,6,8,20,13};
        System.out.println("Minimum difference : "+getMinimumDif(arr, arr.length));
    }
}

Minimum difference : 2

Complexity Analysis 

Time Complexity

Since we are using a sorting algorithm we have O(n Log n) time complexity, where “n”  is the number of elements in the array.

Space Complexity

O(n) where “n”  is the number of elements in the array. Here, we use an array for input making it linear in space complexity.