Minimum Difference in an Array

Easy
0/40
profile
Contributed by
35 upvotes
Asked in companies
OlaGrowwMercedes-Benz Research and Development India

Problem statement

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’.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
4
1 8 3 10   
2
5 5
Sample Output 1 :
2
0
Explanation Of Sample Input 1 :
For test case 1, 
Out of all pairs (1,3) and (8,10) have the minimum difference ‘2’ so the answer is ‘2’.
For test case 2,
There is only one possible pair (5,5) so the answer is ‘0’.
Sample Input 2 :
2
3
8 1 8
2
-3 3
Sample Output 2 :
0
6
Hint

Can you go through all pairs and find the best answer?

Approaches (2)
Bruteforce

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])’.
  • Return ‘ANS’.
Time Complexity

O( N^2 ), where ‘N’ is the size of array ‘ARR’.

There is a total of ‘(N * (N - 1))/2’ pairs, so the overall time complexity is O(N^2).

Space Complexity

O( 1 ), where ‘1’ is constant space.

No extra space is used in the following approach so the overall time complexity is O(1).

Code Solution
(100% EXP penalty)
Minimum Difference in an Array
Full screen
Console