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 [3]:
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 [4]:
assert minimum_absolute_difference([4, 2, 1, 3]) == [[1, 2], [2, 3], [3, 4]]
In [5]:
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 [6]:
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 [7]:
assert minimum_absolute_difference([4, 2, 1, 3]) == [[1, 2], [2, 3], [3, 4]]
In [8]:
assert minimum_absolute_difference([1, 4, 6, 8]) == [[4, 6], [6, 8]]