Find a pair with a minimum absolute difference in an array

By | December 30, 2021

Problem

Given an unsorted array, find the minimum difference between any pair in a given array and print the array.

[1, 2, 2, 1]

1 1

Approach

Sort array in ascending order.

Initialize the difference as INT_MAX.

Compare all adjacent pairs in a sorted array and keep track of the minimum difference and update the pair with minimum difference. This approach takes O(NlogN) time.

C++ Programming

#include <bits/stdc++.h>
using namespace std;

int f, s;

void solve(int arr[], int n)

{

sort(arr, arr+n);

int diff = INT_MAX;

for (int i=0; i<n-1; i++)
if (arr[i+1] - arr[i] < diff)
{
f = arr[i];
s = arr[i+1];
diff = arr[i+1] - arr[i];
}
}

int main()
{
int arr[] = {1, 2, 3, 4};
int n = sizeof(arr)/sizeof(arr);

solve(arr, n);
cout<<f<<" "<<s;
}

1 2

Python Programming

f=-1
s=-1
def solve(arr, n):

arr = sorted(arr)

diff = 10**9
for i in range(n-1):
if arr[i+1] - arr[i] < diff:
diff = arr[i+1] - arr[i]
f=arr[i+1]
s=arr[i]
print(f, end=" ")
print(s)

arr = [1, 2, 3, 4]
n = len(arr)
solve(arr,n)

2 1

Java Programming

import java.util.Arrays;

class Solution
{
static void solve(int[] arr, int n)
{
Arrays.sort(arr);

int diff = Integer.MAX_VALUE;
int f=-1,s=-1;

for (int i=0; i<n-1; i++)
if (arr[i+1] - arr[i] < diff){
diff = arr[i+1] - arr[i];
f=arr[i+1];
s=arr[i];

}
System.out.println(f);
System.out.println(s);

}

public static void main(String[] args)
{
int arr[] = new int[]{1, 2, 3};
solve(arr,3);

}
}

Output

2
1 