Following up on the previous answer, let us say that you have Na elements in list A and Nb elements in list B. You just need to have one hash table. For each element in list A, create a pair with key as an element and an element of vector of values as the number of times that element occurs in it. Use the same hash table to add elements from list B and add second element to the vector of values with the specific value as the number of times that element appears in list B. Now parse that hast table and find all the elements with differing fist and second values of the vector corresponding as the map value. If the vector values differ, those are the specific elements that are different. For elements occurring exclusively in only one of the lists, the size of the vector of values corresponding to that list will be 1. Overall, complexity = O(Na) + O(Nb) + O(M), where M<= Na + Nb. Thus, complexity ~ O(N).