The minimum distance of an unsorted array is mini j i notequ

The minimum distance of an unsorted array is min_i, j i notequalto j |Ai] - A[j]|. Namely, if we sort the array this value is the minimum absolute values of the difference between two contiguous elements. Consider an n times n matrix A. Say that we want to choose one element from every row, A[1, j], A[2, j], A[3, k], ... A[n, p]. The problem is to find an array with minimum distance under this constraint. Namely, we want to find a minimum distance array under the constraint that the first item belongs to the first row, the second item belongs to the second row, and so on. Give al algorithm for the problem.

Solution

import java.util.Arrays;

public class Test{

   // modified version of Binary Search which returns the element closest to \"n\"
   public static int getClosetIndex(int n, int a[]) {

       int start = 0, end = a.length - 1;
       int mid = 0;
       while (start <= end) {
           mid = start + (end - start) / 2;

           if (a[mid] == n)
               return a[mid];
           else if (n < a[mid])
               end = mid - 1;
           else
               start = mid + 1;

       }
       return a[mid];
   }

  
   // main program
   public static void main(String[] args) {

       int n = 5;
       int a[][] = new int[n][n];

       int result[] = new int[n];

       for (int i = 0; i < n; i++) {
           for (int j = 0; j < n; j++) {
               a[i][j] = (int) (Math.random() * 10);
           }
           Arrays.sort(a[i]);
       }
      
      
      
       // Main algorithm starts
       /*
       Step 1 : select an element(say X) from a row(say I)
       Step 2: get the closest pair from other row say P.
       Step 3: if previous min(say MIN) greater than |X-P| , change the candidate to X and MIN = |X-P|.
       Step 4: repeat for each element in row I
       At the end of the jth iteration you will get the candidate from the row I
         
       At the end of the ith iteration you will get the Minimum distance array
       */
       for (int i = 0; i < n; i++) {
           int min = Integer.MAX_VALUE;
           int currentCandidate = Integer.MAX_VALUE;
           for (int j = 0; j < n; j++) {
               for (int k = 0; k < n; k++) {
                   if (i == k)
                       continue;
                   int minPair = getClosetIndex(a[i][j], a[k]);

                   if(Math.abs(a[i][j] - minPair) < min) {
                       min = Math.abs(a[i][j] - minPair);
                       currentCandidate = a[i][j];
                   }
               }

           }
           result[i] = currentCandidate;
       }

      
      
       // display of data
       System.out.println(\"Actual n*n matrix\");
       for (int i = 0; i < n; i++) {
           for (int j = 0; j < n; j++) {
               System.out.print(a[i][j] + \" \");
           }
           System.out.println();
       }
      
       System.out.println(\"Minimum distance Array\");
       for(int i=0;i<n;i++) {
           System.out.print(\"->\"+result[i]);
       }
   }
}