Remove Duplicate Numbers by using a Hash Map

Given a list of integers nums, remove numbers that appear multiple times in the list, while maintaining order of the appearance in the original list. It should use O(k) space where k is the number of unique integers.

Constraints
n ≤ 100,000 where n is the length of nums
Example 1
Input
nums = [1, 3, 5, 0, 3, 5, 8]
Output
[1, 0, 8]
Explanation
Only [1, 0, 8] are unique in the list and that’s the order they appear in.

Remove Duplicate Numbers in a List

We can use a hash table to record the number of appearance for each number in the array. This can be simply done by using the Counter object in Python. Then we go through each key in the Counter to append those elements whose frequency is one.

1
2
3
4
5
6
7
8

class Solution:
    def removeDuplicateNumbers(self, nums):
        c = Counter(nums)
        ans = []
        for i in c:
            if c[i] == 1:
                ans.append(i)
        return ans

class Solution:
    def removeDuplicateNumbers(self, nums):
        c = Counter(nums)
        ans = []
        for i in c:
            if c[i] == 1:
                ans.append(i)
        return ans

We can enumerate over the items properties.

1
2
3
4
5
6
7
8

class Solution:
    def removeDuplicateNumbers(self, nums):
        c = Counter(nums)
        ans = []
        for a, b in c.items():
            if b == 1:
                ans.append(a)
        return ans

class Solution:
    def removeDuplicateNumbers(self, nums):
        c = Counter(nums)
        ans = []
        for a, b in c.items():
            if b == 1:
                ans.append(a)
        return ans

Or simply using the Python’s one-liner via filter and lambda.

1
2
3
4

class Solution:
    def removeDuplicateNumbers(self, nums):
        c = Counter(nums)
        return list(filter(lambda i: c[i] == 1, nums))

class Solution:
    def removeDuplicateNumbers(self, nums):
        c = Counter(nums)
        return list(filter(lambda i: c[i] == 1, nums))

Time complexity is O(N) and space complexity is O(N) where N is the number of elements in the array.

–EOF (The Ultimate Computing & Technology Blog) —