Finding the minimum difference between any two elements from a given array is a basic DSA implementation-based problem that can be solved using the concept of array traversal and sorting. Here first, we will discuss the brute force approach and then the optimized method.
Problem statement
You are given an array of integers. You need to find the minimum difference between any pair of integers from the given array.
Input
arr[ 7 ]={5,10,7,2,15,8,20}
Output
minimum difference = 1
Note: Please try to solve the problem first and then see the solution below.
Approaches
Brute force approach
This approach will find differences between all possible pairs of elements in the array and store the minimum difference.
Dry Run
Code
// C++ code for finding the minimum difference between any pair of elements from the given array.
#include<bits/stdc++.h>
using namespace std;
// brute force approach to find the minimum difference
int minDiffPair(int arr[],int n)
{
int a,b;
int mn=INT_MAX;// variable to store min difference
// finding difference from all possible pairs of elements
for(int i=0;i<n-1;i++)
{
for(int j=i+1;j<n;j++)
{
mn=min(mn,abs(arr[i]-arr[j]));
}
}
return mn;
}
// driver code
int main()
{
int arr[7]={5,10,7,2,15,8,20};
cout<<"minimum difference between two elements: "<<minDiffPair(arr,7);
}
For the above approach time, complexity is O(n2), and space complexity is O(1) as no extra space is used.
Optimized approach
To implement this method, we will first sort the array to reduce the difference between adjacent elements in the array.
Then iterate the array and find the minimum difference between two adjacent elements.
Code
// C++ code for finding the minimum difference between any pair of elements from the given array.
#include<bits/stdc++.h>
using namespace std;
//optimized approach to find the minimum difference
int minDiffPairValue(int arr[ ],int n)
{
int a,b;
int mn=INT_MAX; // variable to store min difference
// sorting the array to reduce difference between adjacent elements
sort(arr,arr+n);
// finding minimum difference from differences of adjacent elements
for(int i=0;i<n-1;i++)
{
mn=min(mn,abs(arr[i]-arr[i+1]));
}
return mn;
}
// driver code
int main()
{
int arr[7]={5,10,7,2,15,8,20};
cout<<"minimum difference between two elements: "<<minDiffPairValue(arr,7);
}
output
minimum difference between two elements: 1
Complexity analysis
For the above approach time, complexity is O(nlogn), and space complexity is O(1) as no extra space is used.
FAQs
Which sorting algorithm is used to implement the STL sort() function? It uses a hybrid algorithm of quick sort, heap sort, and insertion sort. But by default, it is Quicksort that takes O(nlogn) in the worst case.
What is the STL abs() function? This function takes an integer as input and returns the absolute value of the integer.
Key Takeaways
This article covered two approaches to solve the problem, find the minimum difference between any two elements, and corresponding C++ code is also shown.
Check out the Coding Ninjas Studio library for getting a better hold of the data structures and algorithms.
If you want to practice such problems to get a good grasp on such concepts, then you can visit our Coding Ninjas Studio and also explore various topics like DSA, Web Technologies, Programing Fundamentals, Aptitude, and much more from our CN Library | Free Online Coding Resources.
39+ registered 