Discussion on: Daily Challenge #273 - Remove Duplicates

Here's my python solution O(n). The idea is to iterate over the input and keep track of the index of the last time you saw a given number. If you see a number, replace the old value with None, and do a second pass at the end to remove all the Nones.

The two-phase approach is necessary to keep it O(n). If we remove items as we find them it could end up costing O(n^2).

def solve(arr):
    last_seen = {}
    res = []

    for val in arr:
        if val in last_seen:
            res[last_seen[val]] = None
        last_seen[val] = len(res)
        res.append(val)

    return list(v for v in res if v is not None)