How to quickly find the first k minimum differences between any two number in a list with duplicates?

Question

I was trying to find the first k minimum differences between any two numbers in a list, and the list contains duplicates so the output contains duplicates as well. I came up with an algorithm but it takes O(n^2) time complexity. So I am wondering if there is a way to reduce the time complexity down to potentially O(n) or O(nlogn).

I know there are a lot of posts about finding the minimum difference between two numbers in an array (such as one), but I could not really find any optimized solution on returning the first k minimum differences.

PS: I want to return the minimum differences in an ascending order

Below is my code:

public static List<Integer> findMinimumDifferences(List<Integer> list, int k){
    //take care of empty list and k=0
    if(list.isEmpty() || k==0) {
        return null;
    }
    
    //initialize a list to store all the possible pair of differences
    List<Integer> record=new ArrayList<>();
    
    //loop through the input list to find all the absolute differences between any pair of numbers
    for (int i = 0; i < list.size()-1; i++) {
        for (int j = i+1; j < list.size(); j++) {
            //take the absolute difference value and add it into the record
            record.add(Math.abs(list.get(i)-list.get(j)));
        }
    }
    
    //sort the record in ascending order.
    Collections.sort(record);
    
    //initialized a list to store the first k minimum values to return
    List<Integer> ans=new ArrayList<>();
    
    //get the first k minimum values from the sorted list
    for(int i=0;i<k;i++) {
        ans.add(record.get(i));
    }
    
    //return the first k minimum differences in a list
    return ans;
}

Please let me know if there is a way to optimize it to make it run faster.

Answer 1

1. sort the array a[n] ascending ~O(n.log(n))

2. abs derivate array O(n)

   for (i=n-1;i>0;i--)
    a[i] = abs(a[i]-a[i-1]);
   a[0]=0; // ignore first element
   

   however as @greybeard points out the array is already sorted so non need for the abs:

   for (i=n-1;i>0;i--)
    a[i] = a[i]-a[i-1];
   a[0]=0; // ignore first element
   

3. sort the array a[n] ascending ~O(n.log(n))

4. now a[1],a[2],...,a[k] is your answer O(k)

   note that I skipped a[0] ...

resulting in ~O(n.log(n)) complexity