0
$\begingroup$

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]]
| cite | improve this question | |
$\endgroup$
  • 1
    $\begingroup$ When you say "sorted", do you mean "in increasing order", or "in the order they appeared in the input"? (In your example these are the same order, so it's not obvious which you want.) The latter is much easier to do efficiently with the data structures in Python. For the former, you probably need to make a call to sorted at the end to get things in the right order. $\endgroup$ – Blckknght Nov 30 '17 at 7:43
  • $\begingroup$ "in increasing order" as in the example. $\endgroup$ – David Nov 30 '17 at 8:01
  • $\begingroup$ Note that Python is offtopic here. $\endgroup$ – Raphael♦ Nov 30 '17 at 8:04
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks, but it seems to me that the part “in mapping” is a search that takes lineal time. And that is inside the for loop, so the overall time complexity would be quadratic. Or am I ignorant again? $\endgroup$ – David Nov 30 '17 at 8:58
  • $\begingroup$ The worst-case performance of this heavily depends on the implementation. $\Theta(n^2)$ and $\Theta(n \log n)$ are both possible. $\endgroup$ – Raphael♦ Nov 30 '17 at 10:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.