You are watching: Find most frequent element in an array c++
For example:
Input: A<> = 3, 9, 1, 3, 6, 3, 8, 1, 6
Output: 3
Input: A<> = 1, 9, 1, 3, 2, 3, 10
Output: 1
Possible questions to ask the interviewer:-
What must I return if two or an ext elements have the best frequency? (Ans: Return whichever facet is the smallest)Can an unfavorable numbers exist in the array? (Ans: Yes, lock can)Brute force and also Efficient SolutionsWe will comment on three possible solutions because that this problem:-
Brute Force: calculation frequency using nested loopsUsing Sorting: calculation frequency linearly after ~ sortingUsing Hash Table : use a Hash Table to discover the frequency the elements1. Brute force ApproachFor each element, scan the entire variety to uncover its duplicates. Maintain two variables max_freq and ans to store the maximum frequency and the element with the frequency respectively.
Pseudo-Codeint findMostFrequentElement(int A<>, int n){ int max_freq = 0 int ans = -1 for (i = 0 to n-1) { int curr_freq = 1 for (j = i+1 come n-1) if (A
Space Complexity: O(1)
Critical ideas to think!According come this algorithm, the frequency is calculate again top top encountering the 2nd occurrence of an element. Just how should we optimize this such the frequency is calculate only when for each unique element?How can we enhance the time intricacy further? 2. Utilizing SortingIf we kind the array, every the duplicate elements will gain lined up beside each other. We can now linearly uncover the frequency the all aspects in the array. This approach additionally ensures that frequency is calculation only when for each unique element.
Pseudo-Codeint findMostFrequentElement(int A<>, int n){ sort(A, n) int max_freq = 0 int ans = -1 int ns = 0 when (i Complexity AnalysisTime Complexity: Sorting the variety + linear Traversal of array
= O(nlogn) + O(n) = O(n)
Space Complexity: O(n), if we usage merge sort and O(1) if we usage heap sort
Critical concepts to think!If the frequency that the current aspect is equal to the preferably element, is it crucial to check if the current element is smaller than ans?How might you usage the concept of time-space tradeoff to your benefit and find the frequency that all aspects faster?3. Using Hash TableWe can create a hash table and also store elements and also their frequency counts as vital value pairs.
Solution Steps1. Create a Hash Table to save frequency of each aspect in the provided array. Consider aspects in the selection as an essential and your frequency together value2. Very first scan the selection one by one and check if value connected with any an essential (as that certain element) exist in the Hash Table or not
If exist, increment the value of that an essential by 1If not, store the value as 13. Throughout the iteration, we are also storing the most regular element and its frequency in the parameter ans and also max_freq respectively.4. Upgrade ans and max_freq if any kind of value (frequency for the element) higher than the save frequency is found.
See more: Answered: Consumers Express Self-Interest When They A Seek The
5. And finally, return the most frequent facet found i.e. Return ans
int findMostFrequentElement(int A<>, int n){ develop a HashTable H int max_freq = 1 int ans = -1 because that (i = 1 to n-1) { if (A in H) { H> = H> + 1 if (max_freq Complexity AnalysisTime Complexity: O(n) (Why?)
Space Complexity: O(n), because that storing the Hash Table
Critical ideas to think!Is using a sophisticated data structure prefer BST helpful here? analysis the intricacy in that case.What if all aspects were unique, i.e, the maximum frequency is 1, will certainly this code return output as expected? What changes will friend make?Comparison of various solutions
Suggested troubles to solveFind the most constant word in a sentenceSort characters by frequencyFind the frequency of every words in a sentenceFind the the very least frequent element in the arrayFind the height k frequent facets in the arrayFind the the smallest subarray through all events of the most frequent element
If you have any an ext approaches or you uncover an error/bug in the above solutions, please comment down below.