I have an array of numbers 3,1,3,5 and a number k with the value 3. I want to find pairs whose absolute adjacent difference between them is the smallest. Find k such pairs.

All possible pairs are :

|3 - 1| = 2
|3 - 3| = 0
|3 - 5| = 2
|1 - 3| = 2
|1 - 5| = 4
|3 - 5| = 2

For smallest k = 3 values are [0,2,2] is the required answer

My approach:

public static List<Integer> process(List<Integer> list, int k) {
    int n = list.size();
    List<Integer> all = new ArrayList<>();
    Collections.sort(list);
    for(int i=0; i<n; i  ) {
        for(int j=i 1; j<n; j  ) {
            all.add(list.get(j) - list.get(i));
        }
    }
    Collections.sort(all);
    List<Integer> answer = new ArrayList<>();
    for(int i=0; i<k; i  ) {
        answer.add(all.get(i));
    }
    
    return answer;
}

Here I am trying to get all possible pairs and then get the smallest values. so time complexity is more for this program. How to reduce time complexity for this task.

CodePudding user response：

1. Create a max heap/priority queue of size k.
2. Use a nested loop to iterate over all possible differences.
3. For each difference between consecutive elements, push the difference to the heap if heap.max > difference

O(n^2) for iteration, O(n^2 logk) for heap.
Total time complexity: O(n^2 logk)
Total space complexity: O(k) (for heap)

In your approach, you've sorted the list of all n^2 differences, so that has a complexity of O(n^2 logn).

CodePudding user response：

Here is a Python solution. It is somewhat similar to what was already suggested, except that putting values back into the heap allows non-adjacent differences to also be discovered.

Translation to Java left as an exercise for the reader.

import heapq
def closest_differences (elements, limit=None):
    e = sorted(elements)
    best = []
    for i in range(len(elements)-1):
        best.append((e[i 1] - e[i], i, i 1))

    heapq.heapify(best)
    yielded = 0
    while 0 < len(best):
        value, i, j = heapq.heappop(best)
        yield value
        yielded  = 1
        if limit is not None and limit <= yielded:
            break
        if j 1 < len(e):
            heapq.heappush(best, (e[j 1] - e[i], i, j 1))


for d in closest_differences([3, 1, 3, 5], 3):
    print(d)