equalize_array.py

# source: https://www.hackerrank.com/challenges/equality-in-a-array/problem
# video: https://youtu.be/CLIVaqu39wU

def equalizeArray(arr):
    # keep dict of counts
    counts = {}
    # keep highest count item
    highest_count_item = arr[0]
    # loop through list to take counts
    for item in arr: # O(n)
        if item not in counts:
            counts[item] = 0
        counts[item] += 1
        
        # checking if highest count
        prev_highest_count = counts[highest_count_item]

        if prev_highest_count < counts[item]:
            highest_count_item = item
    
    counts.pop(highest_count_item)
            
    return sum(counts.values()) # O(n)
    # Total Time Complexity = O(n) + O(n) = O(2n) => O(n)