**CONTEST CODE** : CYPH2021

**PROBLEM LINK** : CodeChef: Practical coding for everyone

**PROBLEM CODE** : MINHIG

**Author**: Avdhoot Ubale

**Tester**: Avdhoot Ubale

**Editorialist**: Avdhoot Ubale

**DIFFICULTY** : Easy

**PREREQUISITES** : Array/Vectors, Sorting, Implementation Skills

**PROBLEM** :

Given an Array of heights of boxes we need to find pairs of boxes with minimum difference between their heights

**EXPLANATION** :

The naive solution for this problem is to use two loops. For every number a[i], loop over all the numbers to find the optimum number b[i] where (a[i] - b[i]) is minimum. Then, choose the minimum value among all the pairs. This solution has a time complexity O(N2) which will cause the Time Limit Exceeded issue. Therefore, you need to think in another way to find the closest number.

Sort the input array in ascending order. The closest number b[i] to a number a[i] will be either the number before or after it in the list. Calculate the difference between every successive pair and find the minimum value of the difference.

Again loop through the array to print those pairs whose difference between heights is minimum.

*Time Complexity: O(N*logN)*

*Space Complexity: O(N)*

**Solution:**

```
#include <bits/stdc++.h>
using namespace std;
int main(){
int n,p;
cin>>n;
vector<int>a;
for(int i=0;i<n;i++){
cin>>p;
a.push_back(p);
}
sort(a.begin(),a.end());
int min=abs(a[0]-a[1]);
for(int i=0;i<n-1;i++){
if(abs(a[i]-a[i+1])<min){
min=abs(a[i]-a[i+1]);
}
}
for(int i=0;i<n-1;i++){
if(abs(a[i]-a[i+1])==min){
cout<<a[i]<<" "<<a[i+1]<<" ";
}
}
return 0;
}
```