How can I find the closest pair with the smallest difference in a single array?

Question

I have a code that creates a list of 20 random integers between 1 and 1000. And In the case of multiple existences of closest pair, I have to display the smallest pair.

This is what I have so far:

import random

numbers = [random.randint(1, 100) for num in range(20)]
print(numbers)

Answer 1

Sort and find the pair of adjacent numbers with the minimum difference:

from itertools import pairwise

result = min(pairwise(sorted(numbers)),
             key=lambda pair: pair[1] - pair[0])

Before Python 3.10:

numbers.sort()
result = min(zip(numbers, numbers[1:]),
             key=lambda pair: pair[1] - pair[0])

Answer 2

If I understand the problem correctly, you get something like: Output:

[38, 88, 57, 19, 54, 13, 90, 99, 6, 87, 56, 42, 51, 77, 67, 77, 17, 31, 7, 87]

by your code and you want to find the two numbers that have the smallest difference?

I would start off by sorting the list:

sorted_list = sorted(numbers)

Output:

[6, 7, 13, 17, 19, 31, 38, 42, 51, 54, 56, 57, 67, 77, 77, 87, 87, 88, 90, 99]

Then I would loop over the sorted list and keep track of the difference like in the code below:

min_difference = float('inf')  # initialize the minimum difference with + infinity
result = [None, None]
for i in range(1, len(sorted_numbers)):
    num_a = sorted_numbers[i-1]  # get the element from the previous index. That's why we start off in the for loop at 1
    num_b = sorted_numbers[i]  # get the element from the current index
    difference = num_b - num_a  # calculate the difference. Since you only have positive numbers and the list is sorted this is working. In case you also want to include negative numbers you can write abs(num_b - num_a) to get the absolute difference for two numbers.
    if difference < min_difference:
        min_difference = min(difference, min_difference)  # the built-in min method returns the minimum from the elements passed to it. Here I update the minimum difference.
        result = [num_a, num_b]  # Here I save the two numbers with the minimum difference so far in the results list.
    if num_b - num_a == 0:  # Smallest difference is 0
        break  # Exits the for-loop

print(result)

Output:

[77, 77]

Hope this helps and hope I understood the problem correctly!

Answer 3

Since you only want the smallest pair, what you cant do is sort your list (or of copy of your list depending on your needs) with sort().

import random

numbers = [random.randint(1, 100) for num in range(20)]
numbers.sort()

print(numbers)

Then by iterating over the list, if a number is at more than 1 position, it is the smallest pair, so we can break the loop.

smallestPair = None
for n in numbers:
    indices = [i for i, x in enumerate(numbers) if x == n]
    if len(indices) > 1: # means there is more than 1 occurence of this number
        smallestPair = n
        break

print(smallestPair)