Minimum Absolute Difference (via Leetcode)¶

Date published: 2020-04-12

Category: Python

Subcategory: Beginner Algorithms

Tags: functions, loops, lists

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]]

# 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]]

# 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

# 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

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]]

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]]

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

# 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

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]]

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]]

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