Monday, July 24, 2017

Closest Pair of elements in sorted array


import java.util.Arrays;
import java.util.Random;

public class ClosestPair {
    public static void main(String[] argv){
        Random random = new Random();
        int[] nums = new int[10];
        for(int i = 0; i< 10; i++) {
            nums[i]= random.nextInt(1000);
        }
        ClosestPair closestPair = new ClosestPair();
        int[] pair = closestPair.closestPair(nums);
        System.out.println(Arrays.toString(pair));
    }

    /*
        Problem: Given sorted array find the closest pair of elements
        Solution: First sort the array then perform a linear search with 2 elements at a time to find out
        difference between n and n-1 while maintaining smallest difference
     */
    public int[] closestPair(int[] nums){
        Arrays.sort(nums);
        int minDiff = Integer.MAX_VALUE;
        int[] closestPair = new int[2];
        for(int i = 1; i < nums.length; i++){
            int diff = Math.abs(nums[i]-nums[i-1]);
            if(diff <minDiff){
                closestPair[0] = nums[i-1];
                closestPair[1] = nums[i];
                minDiff = diff;
            }
        }
        return closestPair;
    }
}

No comments:

Post a Comment