Teaching Kids Programming – Remove Last Duplicate Entries (Hash Table)

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given a list of integers nums, find all duplicate numbers and delete their last occurrences.

Constraints
0 ≤ n ≤ 100,000 where n is the length of nums
Example 1
Input
nums = [1, 3, 4, 1, 3, 5]
Output
[1, 3, 4, 5]
Example 2
Input
nums = [1, 1, 1, 2, 2, 2, 3, 3, 3]
Output
[1, 1, 2, 2, 3, 3]

Keep track of numbers that are duplicates. And create a new list based on that data structure.

Remove Last Duplicate Entries (Hash Table)

Instead of Deletion, we can go through numbers and append those who are to keep: only appearing once or it is not the last occurence. We can use one hash table (Counter) to count how many times each number appears and another hash table to remember the last appearing index.

1
2
3
4
5
6
7
8
9

class Solution:
    def solve(self, nums):
        res = []
        x = Counter(nums)
        d = {v: i for i, v in enumerate(nums)}
        for i, v in enumerate(nums):
            if d[v] != i or x[v] == 1:
                res.append(v)
        return res

class Solution:
    def solve(self, nums):
        res = []
        x = Counter(nums)
        d = {v: i for i, v in enumerate(nums)}
        for i, v in enumerate(nums):
            if d[v] != i or x[v] == 1:
                res.append(v)
        return res

The time complexity is O(N) – we need to traverse the array three times. The space complexity is O(N) as we are using two hash tables.

–EOF (The Ultimate Computing & Technology Blog) —