Remove duplicates of first elements of pairs

Question

A list of pairs is given using Python. I want to remove duplicate occurrences of the first element of the pair leaving only one occurrence of each first element paired with the highest second element it comes with. I am looking for an efficient solution that returns the pairs sorted.

>>> myfunc([[2, 0], [3, 0], [4, 0], [5, 0], [3, 2], [4, 0], [5, 3], [5, 3]])
[[2, 0], [3, 2], [4, 0], [5, 3]]

Answer 1

You can do this pretty easily in $O(n log(n))$ time by using a hash table (such as Python's dict) to map from the first value in a pair to the largest second value it's been seen with.

def myfunc(pairs):
   mapping = {}
   for key, value in pairs:
       if key not in mapping or value > mapping[key]:
           mapping[key] = value
   return sorted(mapping.items())

Hash table lookups take $O(1)$ time on average, so eliminating the duplicates in the loop will take $O(n)$ time. Sorting is (asymptotically) slower, taking $O(n log(n))$ time.