Find a pair with a minimum absolute difference in an array

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:

• Construct a tree from Inorder and Level order traversals
• Print all subarrays with 0 sum
• Rearrange an array in maximum minimum form
• Rod Cutting Problem
• Shuffle list in Python using random.shuffle() function
• Longest Consecutive Sequence in Linear time
• Count subarrays with given XOR
• Minimum Edit Distance
• Majority Element
• Rearrange an array such that arr[i] = i