find the pairs of elements that have the smallest absolute difference between them

To find the pairs of elements that have the smallest absolute difference between them, If there are multiple pairs, then find them all in a given list of unsorted integers, A = {a1,a2,...,aN}.

Constraints:

• 2≤N≤200000
• −107≤ai≤107
• ai≠aj,where 1≤i<j≤N

I had taken input format in slightly different manner:

The first line of input contains a single integer, N, representing the length of list A.

In second line, there are N space-separated integers a1,a2,....,aN.

Example.

10 -20 -39134237 -345620 -3625601 7375619 -7389761 30 6236457 -6456494 996854

And the output :

Single line contains the pairs of elements having the smallest absolute difference.

Example

-20 30



Solution:

1. We need to sort the given list of elements in ascending or descending order. Here i will use quick sort and sort in ascending order.'ar' is the unsorted array.

static void partitioning(int[] ar, int left, int right) {
 if (left >= right) return;
 else {
  int p = ar[right];
  int i = left, j = left;
  while (j < right) {

   if (ar[j] > p) {
    j++;
    continue;
   } else {
    swap(ar, i, j);
    i++;
    j++;
   }
  }
  int temp = ar[i];
  ar[i] = ar[j];
  ar[j] = temp;
  partitioning(ar, left, i - 1);
  partitioning(ar, i + 1, right);

 }

}

private static void swap(int[] ar, int i, int j) {

 if (i >= j) return;
 else {

  int temp = ar[j];
  ar[j] = ar[i];
  ar[i] = temp;
 }
}

2.This is the main step.

   a. Now we have sorted array in ascending order , the minimum absolute difference will always be between the two consecutive elements.

   b. So we have to calculate the difference between all the consecutive pairs of the sorted list and the pairs having the minimum difference will be printed as output. Below method is finding those pairs and adding in a string(since we only need to print them). 'ar' is the sorted array

int min = Integer.MAX_VALUE;
String result = "";
for (int j = 1; j < ar.length; j++) {
 if (ar[j] - ar[j - 1] < min) {
  min = ar[j] - ar[j - 1];
  result = Integer.toString(ar[j - 1]) + " " + ar[j];
 } else if (ar[j] - ar[j - 1] == min) {
  result += " " + Integer.toString(ar[j - 1]) + " " + ar[j];
 }
}
System.out.print(result);

Following java program will use above methods to give solution to our problem

import java.util.*;
public class ClosestNumber {


 static void partitioning(int[] ar, int left, int right) {
  if (left >= right) return;
  else {
   int p = ar[right];
   int i = left, j = left;
   while (j < right) {

    if (ar[j] > p) {
     j++;
     continue;
    } else {
     swap(ar, i, j);
     i++;
     j++;
    }
   }
   int temp = ar[i];
   ar[i] = ar[j];
   ar[j] = temp;
   partitioning(ar, left, i - 1);
   partitioning(ar, i + 1, right);

  }

 }

 private static void swap(int[] ar, int i, int j) {

  if (i >= j) return;
  else {

   int temp = ar[j];
   ar[j] = ar[i];
   ar[i] = temp;
  }
 }


 private static Scanner in = new Scanner(System. in );

 public static void main(String[] args) {

  int n = in .nextInt(); in .nextLine();
  String numbers = in .nextLine();
  StringTokenizer st = new StringTokenizer(numbers, " ");
  int[] ar = new int[n];
  int i = 0;
  while (st.hasMoreTokens()) {
   ar[i] = Integer.parseInt(st.nextToken());
   i++;
  }
  partitioning(ar, 0, (ar.length - 1));

  int min = Integer.MAX_VALUE;
  String result = "";
  for (int j = 1; j < ar.length; j++) {
   if (ar[j] - ar[j - 1] < min) {
    min = ar[j] - ar[j - 1];
    result = Integer.toString(ar[j - 1]) + " " + ar[j];
   } else if (ar[j] - ar[j - 1] == min) {
    result += " " + Integer.toString(ar[j - 1]) + " " + ar[j];
   }
  }
  System.out.print(result);
 }
}