|
Be the first user to complete this post
|
Add to List |
216. Find the element which appears maximum number of times in the array
Objective: Given an array of integers, write an algorithm to find the element which appears a maximum number of times in the array.
This problem can also be referred as "Most frequent Element in the array"
Example:
int [] arrA = {4, 1, 5, 2, 1, 5, 9, 8, 6, 5, 3, 2, 4, 7};
Output: Element repeating maximum no of times: 5, maximum count: 3
Approach:
Naive approach: Use 2 loops. Check each element in the array with all other elements in the array and keep track of its count also maintain the max counter which tracks the element and repeats the maximum number of time.
Time Complexity : O(n^2) Space Complexity: O(1)
Sorting approach: Sort the array, this will bring all the duplicates together if present. Now navigate the array and keep track of its count and also maintain the max counter which tracks the element repeats the maximum number of times.
Time Complexity: O(nlogn) Space Complexity: O(n) by using merge sort.
Better Solution : Use Hashmap. Store the count of each element of array in a hash table and later check in Hash map which element has the maximum count - Find duplicates in an given array
Time Complexity: O(n) and Space Complexity: O(n).
Better Solution (Conditional): O(n) time and O(1) extra space.
- This solution works only if the array has positive integers and all the elements in the array are in the range from 0 to n-1 where n is the size of the array.
- Navigate the array.
- Update the array as for ith index :- arrA[arrA[i]% n] = arrA[arrA[i]% n] + n;
- Now navigate the updated array and check which index has the maximum value, that index number is the element that has the maximum occurrence in the array.
- See the picture below for more explanation.
A similar approach used in problem: if array has all consecutive numbers.
Output:
Element repeating maximum no of times: 5, maximum count: 3