Find the minimum difference of the 2 elements from the remaining array while iterating python

Question

I am iterating through the array and every time I would like to find 2 elements with the minimum difference from the remaining array. e.g given array=[5,3,6,1,3], if iterator i is at index 2 so array[i]=6, I would like to find the minimum difference that 2 elements from the array excluding 6 could give.

I was thinking of finding first and second maximum elements for every iteration, but I do not know how to ignore array[i] element. Any tips would be appreciated.

Answer 1

On the outer loop, track the index using enumerate(). Then on the inner loop which iterates the rest of the items (to get the minimum difference), also track the index so that we can skip it if it is equal to the outer loop's index.

Here are some solutions for you. We don't need to get all the differences of all pairs of numbers as that would result to a factorial time complexity (since we will get all possible combinations/pairs). What we can do is simply sort the array, then once sorted

1. We only need to get the difference of each consecutive number e.g. [1, 3, 10, 11, 12] we just need to subtract 3 - 1, 10 - 3, 11 - 10, and 12 - 11. There is no more point of doing e.g. 12 - 1 because we are sure that it would be greater than any of the consecutive pairs.
2. Aside from consecutive pairs, we also need to get alternating pairs so that if we removed a number, we will still consider the difference of its previous and next e.g. [10, 12, 14]. If we are at item 12, then 12 -10 and 14 - 12 shouldn't be considered. But 14 - 10 should be!

Solution 1

A bit complicated, but is only O(n log n) in time complexity.

• Sort the array. The sorted values must contain the original indices.
• Store the differences in sorted order, but keep it at a maximum of 3 items only wherein those 3 items are the least differences (same idea with bounded min heaps).
  • Why 3 items? Say for example we have [1, 10, 12, 14, 100]. Then we know that the minimum difference is 2 which is the result of 12 - 10 and 14 - 12. For item 1, the min diff is 2, same with items 10, 14, and 100. But for 12, it shouldn't be 2 because if we remove 12, the next min diff is 14 - 10 which is 4. This would be the worst case. So we need to store maximum of 3 minimum differences, which here will be 2 from 12 - 10, 2 from 14 - 12, and 4 from 14 - 10 so that we can catch the case for 12 which should pick the third option (4 from 14 - 10).
• Iterate the original array. For each item, see the first applicable difference and display it. This would be the difference that wasn't a result of using the current item in the subtraction.

from bisect import insort

numbers = [14, 10, -11, 27, 12, 4, 20]
numbers_sorted = sorted(enumerate(numbers), key=lambda value: value[1])  # O(n log n)

differences = []
for index in range(1, len(numbers_sorted)):  # O(n), the binary search and pop on <differences> are negligible because it is fixed at the constant size of 3
    for prev in range(1, 2 if index == 1 else 3):  # Subtract consecutive and alternating
        diff_tup = (
            numbers_sorted[index][1] - numbers_sorted[index-prev][1],
            numbers_sorted[index-prev],
            numbers_sorted[index],
        )
        insort(differences, diff_tup)
        if len(differences) > 3:
            differences.pop()

for index, num in enumerate(numbers):  # O(n), the iteration of <differences> is negligible because it is fixed at the constant size of 3
    for diff in differences:
        if index != diff[1][0] and index != diff[2][0]:
            print(f"{num}: min diff {diff[0]} from {diff[1][1]} and {diff[2][1]}")
            break

Solution 2

More straight-forward, but is O(n ^ 2) in time complexity.

• Sort the array. The sorted values must contain the original indices.
• Iterate the array in the primary loop.
  • For each item, iterate the sorted array.
    • Skip if the item if it is the one in the primary loop.
    • Otherwise, subtract the numbers.
    • If it is less than the current minimum, set it as the new minimum.
  • Display the minimum for the current number

from bisect import insort

numbers = [14, 10, -11, 27, 12, 4, 20]
numbers_sorted = sorted(enumerate(numbers), key=lambda value: value[1])  # O(n log n)

for num_index, num in enumerate(numbers):  # O(n ^ 2)
    min_diff = None
    min_subtractors = None
    
    for index in range(1, len(numbers_sorted)):
        for prev in range(1, 2 if index == 1 else 3):  # Subtract consecutive and alternating
            if num_index == numbers_sorted[index][0] or num_index == numbers_sorted[index-prev][0]:
                continue
            diff = numbers_sorted[index][1] - numbers_sorted[index-prev][1]
            if min_diff is None or diff < min_diff:
                min_diff = diff
                min_subtractors = (numbers_sorted[index-prev][1], numbers_sorted[index][1])

    print(f"{num}: min diff {min_diff} from {min_subtractors[0]} and {min_subtractors[1]}")

Output

14: min diff 2 from 10 and 12
10: min diff 2 from 12 and 14
-11: min diff 2 from 10 and 12
27: min diff 2 from 10 and 12
12: min diff 4 from 10 and 14
4: min diff 2 from 10 and 12
20: min diff 2 from 10 and 12