Last Updated: 20 May, 2022
Minimum Difference in an Array
Easy
Asked in companies
Given an array of integers, print the minimum of the absolute difference of all possible pairs of elements.
Example :
N = 5
ARR = [ 3, -6, 7, -7, 0 ]
Out of all pairs, (-7,-6) have a difference of ‘1’, and no other pair has less difference. So ‘ANS’ is ‘1’.
Input Format :
The first line contains a single integer ‘T’ denoting the number of test cases. The test cases are as follows.
The first line of each test case contains integer ‘N’ denoting the size of the array ‘ARR’.
The second line contains ‘N’ integers denoting the integers of array ‘ARR’.
Output format :
For each test case, print the minimum difference of all possible pairs in ‘ARR’.
Note :
You don’t need to print anything. It has already been taken care of. Just implement the given function.
Constraints :
1 <= T <= 10
2 <= N <= 10^5
-10^8 <= ARR[i] <= 10^8
Sum of N <= 10^5
Time Limit: 1 sec
Approaches
APPROACH :
- We will use a brute force approach to solve this problem.
- We will go through all pairs using two loops, we will find the minimum absolute and best answer.
ALGORITHM :
- Create a variable ‘ANS’ with a value of ‘INF’.
- Start iterating from ‘i = 0’ till ‘i < N’.
- Start iterating from ‘j = i + 1’ till ‘j < N’.
- Set ‘ANS’ as the minimum of ‘ANS’ or ‘ABS(ARR[i] - ARR[j])’.
- Start iterating from ‘j = i + 1’ till ‘j < N’.
- Return ‘ANS’.
APPROACH :
- Let us sort the array in non-decreasing order.
- Now for each element ‘i’ if there exists an element at ‘i-1’, we can say it is the closest smaller element to ‘i’.
- Similarly for ‘i + 1’, we can say it is a closest greater number than ‘ARR[i]’.
- So as we have the closest number for each ‘i’, we will only check these two possible values to find the minimum difference.
- Since if there exist ‘i + 1’ for ‘i’, the ‘i’ act as the previous element for ‘i + 1’, so we will only check ‘i - 1’.
- And find the minimum of all differences.
ALGORITHM :
- Create a variable ‘ANS’ with a value of ‘INF’.
- Sort ‘ARR’ in ascending order.
- Start iterating from ‘i = 1’ till ‘i < N’.
- Set ‘ANS’ as the minimum of ‘ANS’ or ‘ARR[i] - ARR[i - 1]’.
- Return ‘ANS’.