Как удалить дубликаты списка если элементы словари?

Вот код, который выведет уникальные словари в порядке их появления в исходном списке.

dicts = [
    {"key1": "value1"},
    {"k1": "v1", "k2": "v2", "k3": "v3"},
    {},
    {},
    {"key1": "value1"},
    {"key1": "value1"},
    {"key2": "value2"}
]

known_dicts = set()
result = []


for d in dicts:
    items = tuple(d.items())
    if items not in known_dicts:
        result.append(d)
        known_dicts.add(items)

print(result)

Сложность здесь точно будет субквадратичная. И, кажется, даже чуть ли не линейная, если я ничего не упускаю из вида.

Предложенное мной ниже решение не удовлетворяет условию: алгоритмическая сложность не должна быть O(n^2) (спасибо людям в комментариях, которые указали на ошибку) Здесь сложность будет O(n^2).

def remove_duplicate(array: List[dict]) -> List:
    unique_array = []
    for elem in array:
        if elem not in unique_array:
            unique_array.append(elem)
    print(unique_array)

Всё же я хочу предложить другое решение воспользовавшись не строгостью условия о порядке элементов, предполагаю, что у данного алгоритма сложность меньше чем O(n^2):

def remove_duplicate(array: List[dict]) -> List:
    unique_set = {tuple(elem.items()) for elem in array}
    print([dict(elem) for elem in unique_set])