Find a pair with a minimum absolute difference in an array

Posted in /  

Find a pair with a minimum absolute difference in an array

Vinay Khatri
Last updated on July 11, 2022

    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:

    Tags:
    array

    Leave a Comment on this Post

    0 Comments