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.

Sample Input

[1, 2, 2, 1]

Sample Output

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[0]);

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

Output

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)

Output

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

People are also reading:

Author: Vinay

I am a Full Stack Developer with a Bachelor's Degree in Computer Science, who also loves to write technical articles that can help fellow developers.

Leave a Reply

Your email address will not be published. Required fields are marked *