lilys_homework.py

# source: https://www.hackerrank.com/challenges/lilys-homework
# video: https://youtu.be/HmyDuVZoE8Y
def lilysHomework_helper(arr, reverse = False):
    # clone arr, since modifying
    arr = arr[:] # O(n)?
    # arr = [2, 5, 3, 1]
    # store sorted array
    sorted_arr = sorted(arr, reverse = reverse) # O(nlogn)
    #    sorted_arr = [1, 2, 3, 5]
    #              OR [5, 3, 2, 1] if reverse = True

    # create dictionary of values and their indeces
    indeces_by_values = {}

    for i, val in enumerate(arr): # O(n)
        indeces_by_values[val] = i
    # indeces_by_values = {
    #   2: 0,
    #   5: 1,
    #   3: 2,
    #   1: 3
    # }

    # count number of swaps
    counter = 0
    for good_i, curr_val in enumerate(arr): # O(n)
        # good_i = 0, curr_val = 2
        sorted_val = sorted_arr[good_i]
        # sorted_val = 1
        bad_i = indeces_by_values[sorted_val]
        # bad_i = 3

        # swap occurs if bad_i is not good_i
        if bad_i != good_i:
            # swap (NOTE: this modifies the arr)
            arr[bad_i]  = curr_val
            arr[good_i] = sorted_val
            # same as: arr[bad_i], arr[good_i] = arr[good_i], arr[bad_i]

            # arr = [2, 5, 3, 1] => [1, 5, 3, 2]
            # change record for that value
            indeces_by_values[curr_val] = bad_i
            # indeces_by_values => {
            #   2: 3,
            #   5: 1,
            #   3: 2,
            #   1: 3 # don't need to update here
            # }
            counter += 1

    return counter # Time Complexity = O(nlogn)

def lilysHomework(arr):
    forward_count = lilysHomework_helper(arr)
    reverse_count = lilysHomework_helper(arr, reverse = True)
    return min(forward_count, reverse_count) # Time Complexity = O(nlogn)

Nice and clean solution!