Best way to find max occurrence element | Sololearn: Learn to code for FREE!

+1

Best way to find max occurrence element

Task is to find highest frequency element from a input vector Extra space used is O(N) in terms of unordered map Insertion in unordered map is O(1) and preparing map from vector's each element. So, till now time time complexity is O(N) Now we iterate over map linearly to find max element and hence Time complexity : O(N) space complexity : O(N) Can we optimize on this? https://code.sololearn.com/c38bTtpvOFw0

10/1/2021 1:10:50 PM

Ketan Lalcheta

1 Answer

New Answer

+5

This looks fairly efficient to me. FWIW you can also use moore's voting algorithm for more efficiency if it is given that the element with highest frequency exists in majority of the vector ( i.e. frequency is more than half the size of vector ) https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_majority_vote_algorithm