Lowest absolute differences

user_19284394 0
Viewed 78

I saw that this question is already solved here Find pairs with least difference
But I am having a hard time understanding the solution that is given. I understand that the 1st minimum absolute difference will be among the absolute differences of the adjacent terms. After popping the minimal element, it's pushing the new diff into the heap. If the minimal is (i+1)-(i) value, i, j = heapq.heappop(best)then the new one inserted is the absolute difference between (i+2)-(i) this is done at the line heapq.heappush(best, (e[j+1] - e[i], i, j+1)) . For the solution to work, the next minimal absolute difference must be the minimum element in the resulting heap. Why is that the case? Why will the next minimal absolute difference be one in the heap, including the newly pushed element?
If anyone could throw some light on this, it would be great

algorithm
1 Answers

The solution sorts the input list before doing anything else. Let's say that after sorting, the list is {a,b,c}.

There are three differences to consider: b-a, c-a, and c-b.

Because the list is sorted, we know that c-a must be bigger1 than b-a. So the solution only needs to put b-a and c-b into the heap initially.

When b-a is read from the heap, c-a is added to the heap. It works because c-a is bigger than b-a, so c-a can't be read from the heap until b-a is read. Hence, c-a doesn't need to be written into the heap, until after b-a is read.

1: I'm using "bigger" to mean "greater than or equal to"

Example

Consider the array (after sorting) {1,2,10,11,12} with k=4. For clarity, let's assign labels to the elements of the array: a=1, b=2, c=10, d=11, e=12.

There are four sequences that need to be handled. The sequences are:

  seq       labels                  example values       sequence of differences
   A    {b-a, c-a, d-a, e-a}    {2-1, 10-1, 11-1, 12-1}      {1, 9, 10, 12}
   B    {c-b, d-b, e-b}         {10-2, 11-2, 12-2}           {8, 9, 10}
   C    {d-c, e-c}              {11-10, 12-10}               {1, 2}
   D    {e-d}                   {12-11}                      {1}

The first thing to note is that the sequences are in ascending order, because the input array is sorted in ascending order. So the first value in each sequence is necessarily the smallest element in each sequence.

That means we don't need to put all O(n^2) differences into the min-heap. We only need to put the first difference from each sequence into the min-heap. That's because the second difference won't be read from the heap until after the first difference (from the same sequence) is read. So the second difference in a sequence doesn't need to be written to the heap, until after the first has been read. The result is that the heap contains O(n) elements, one element from each sequence.

To finish the example the initial heap is {1,1,1,8}. Those are the first differences from each sequence, shown sorted in the order they'll be read from the heap. The first three outputs are going to be {1,1,1}.
When the 1 from A sequence is read, 9 is added to the heap.
When the 1 from C sequence is read, 2 is added.
When the 1 from D sequence is read, D is done, and nothing is added.

After {1,1,1} has been output, the heap contents are {2,8,9}. The 2 will be read next (and not replaced because 2 is the last of C sequence), and given k=4, the answer is {1,1,1,2}.

user_33861090
Related