For these types of problems you usually assume that every element is unique. The fix is just making two passes through the array instead of one, so it's still O

For these types of problems you usually assume that every element is unique. The fix is just making two passes through the array instead of one, so it's still O(n). It's typically easy to reduce solving such a problem with duplicates allowed into a very similar one without duplicates. Just replace every element x by the ordered pair (x, the position in the array where x came from) and then use a modified comparison function that sorts according to the second element in the pair if two ordered pairs are equal in the first element.