Algorithm to remove duplicates array leaving at most 2 elements My interview question was that I need to return the length of an array that removed duplicates but we can leave at most 2 duplicates. 

For example, [1, 1, 1, 2, 2, 3] the new array would be [1, 1, 2, 2, 3]. So the new length would be 5. I came up with an algorithm with \$O(2n)\$ I believe.

def removeDuplicates(nums):
    if nums is None:
        return 0

    if len(nums) == 0:
        return 0

    if len(nums) == 1:
        return 1

    new_array = {}
    for num in nums:
        new_array[num] = new_array.get(num, 0) + 1

    new_length = 0
    for key in new_array:
        if new_array[key] &gt; 2:
            new_length = new_length + 2
        else:
            new_length = new_length + new_array[key]

    return new_length

new_length = removeDuplicates([1, 1, 1, 2, 2, 3])
assert new_length == 5


Can I improve this code to be any faster?
You're just reimplementing collections.Counter.

def remove_duplicates(lst):
    return sum(min(x, 2) for x in collections.Counter(lst).values())




By the way, \$O(2n)\$ is equivalent \$O(n)\$. However, the bound is actually tighter: \$O(n + m)\$, where m is the number of distinct elements.

This is, however, an average bound, because it relies on a dict. If the worst case hash collisions happen, you get \$O(m(n+m))\$