Python Beginner Algorithms Tutorial

# Minimum Absolute Difference (via Leetcode)

Problem on Leetcode.

Problem statement:

Given a list of distinct integers, find all pairs of items with the minimum absolute difference of any two items.

Return a list of pairs in ascending order with respect to other pairs and the first pair item smaller than the second pair item in each pair.

#### Explanation of Test Cases¶

In [ ]:
# assert minimum_absolute_difference([4, 2, 1, 3]) == [[1, 2], [2, 3], [3, 4]]


The minimum absolute difference between items is 1; see 2-1 which equals 1. There are three pairs of items that have an absolute difference of 1.

In [ ]:
# assert minimum_absolute_difference([1, 4, 6, 8]) == [[4, 6], [6, 8]]


The minimum absolute difference between items is 2; see 6-4 which equals 2. There are two pairs of items that have an absolute difference of 2.

### Solution #1¶

#### Pseudocode¶

In [ ]:
# create a function that takes in a list of integers

# create sorted list of items

# find minimum absolute difference value between comparing consecutive values of sorted list

# create pairs_list to hold final pairs of min absolute pairs

# iterate over items in sorted list:
# compare item to next item...
# if absolute difference of items equals the min:
# append pair as a list to pairs_list

# return pairs list


#### Complexity¶

Time complexity:

• O(nlogn) to sort list of integers.
• O(n) for iteration over all list items to find minimum absolute difference.
• O(n) for iteration over all list items to create pairs that meet minimum absolute difference.

Total time complexity is O(3nlogn). The 3 is insignificant so it's simply O(nlogn).

Space complexity:

• O(n) to store list of sorted integers.
• O(2n) to store final list of pairs because at worst case all items in original list could be included twice.

Total space complexity of O(3n). The 3 is insignificant so it's simply O(n).

#### Code¶

In :
def minimum_absolute_difference(integers_list):
min_absolute_difference = float("inf")

sorted_integers_list = sorted(integers_list)

for index in range(0, len(sorted_integers_list)-1):
small_num = sorted_integers_list[index]
large_num = sorted_integers_list[index+1]
absolute_difference = abs(large_num-small_num)
if absolute_difference <= min_absolute_difference:
min_absolute_difference = absolute_difference

# we have the exact min_absolute_difference
min_pairs_list = []

for index in range(0, len(sorted_integers_list)-1):
small_num = sorted_integers_list[index]
large_num = sorted_integers_list[index+1]
absolute_difference = abs(large_num-small_num)
if absolute_difference == min_absolute_difference:
min_pairs_list.append([small_num, large_num])
return min_pairs_list


#### Run Test Cases¶

In :
assert minimum_absolute_difference([4, 2, 1, 3]) == [[1, 2], [2, 3], [3, 4]]

In :
assert minimum_absolute_difference([1, 4, 6, 8]) == [[4, 6], [6, 8]]


#### Reflection on Solution #1¶

While the code above is clean and works, it's clear there's code that's simply copied and pasted. 5 lines - the for loop to the if statement - are repeated. This is OK as it causes high time complexity and reduced space complexity.

Alternatively, I can devise a solution with decreased time complexity and increase space complexity. This will be solution #2.

### Solution #2¶

#### Pseudocode¶

In [ ]:
# create function that takes in integers list
# sort the list
# min_absolute_difference assigned to a value of positive infinity
# assign min_pairs_list to be empty list

# do one iteration over indices sorted list:
# compare value and previous value (a pair)...
# if absolute difference of pair is equal to min_absolute_difference:
# append pair as list to min_pairs_list
# else if absolute difference pair is less than min_absolute_difference:
# reassign min_absolute_difference to be new absolute difference of pair
# if min_pairs_list is empty:
# append pair as list to min_pairs_list
# else:
# we don't want to keep old pairs in min_pairs_list that contain higher abs value among pairs...
# reassign min_pairs_list to *just* contain one list item as items in this pair
# else:
# absolute min difference of those values is larger than our min...
# we don't want to append this pair to our min_pairs_list
# pass
# return min_pairs_list


#### Code¶

In :
def minimum_absolute_difference(integers_list):
sorted_list = sorted(integers_list)
min_absolute_difference = float("inf")
min_pairs_list = []

for index in range(0, len(sorted_list)-1):
small_num = sorted_list[index]
large_num = sorted_list[index+1]
abs_diff = abs(large_num - small_num)
if abs_diff == min_absolute_difference:
min_pairs_list.append([small_num, large_num])
elif abs_diff < min_absolute_difference:
min_absolute_difference = abs_diff
if len(min_pairs_list) == 0:
min_pairs_list.append([small_num, large_num])
else:
# creates new min_pairs_list with pair items
min_pairs_list = [[small_num, large_num]]
else:
# absolute min difference of pairs is larger than min_absolute_difference
pass

return min_pairs_list


#### Complexity¶

Time complexity:

• O(n) for iteration over all list items
• O(nlogn) to sort list of integers

Total time complexity is O(2nlogn). The 2 is insignificant so it's simply O(nlogn).

Space complexity:

• O(n) to store list of sorted integers
• O(2n) to store final list of pairs because at worst case all items in original list could be included twice

Total time complexity is O(3n). The 3 is insignificant so it's simply O(nlogn).

#### Run Test Cases¶

In :
assert minimum_absolute_difference([4, 2, 1, 3]) == [[1, 2], [2, 3], [3, 4]]

In :
assert minimum_absolute_difference([1, 4, 6, 8]) == [[4, 6], [6, 8]]