-
Notifications
You must be signed in to change notification settings - Fork 0
/
Max_Freq_elem_Hashmap.txt
74 lines (56 loc) · 2.46 KB
/
Max_Freq_elem_Hashmap.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
Maximum Frequency Number
Send Feedback
You are given an array of integers that contain numbers in random order. Write a program to find and return the number which occurs the maximum times in the given input.
If two or more elements contend for the maximum frequency, return the element which occurs in the array first.
Input Format:
The first line of input contains an integer, that denotes the value of the size of the array. Let us denote it with the symbol N.
The following line contains N space separated integers, that denote the value of the elements of the array.
Output Format :
The first and only line of output contains most frequent element in the given array.
Constraints:
0 <= N <= 10^8
Time Limit: 1 sec
Sample Input 1 :
13
2 12 2 11 12 2 1 2 2 11 12 2 6
Sample Output 1 :
2
Sample Input 2 :
3
1 4 5
Sample Output 2 :
1
/*We could iterate through the array, increase the frequency of each element by 1 as we
encounter it (initially the frequency would be 0). Also, we could maintain the maximum
frequency as we iterate through the array.
Now we would know the maximum frequency but we still don’t know which element that
frequency belongs to. There could be multiple elements with the same frequency.
So, we iterate through the array once more and check whether the frequency of the
current element is equal to the maximum frequency we found earlier. If they are equal
we return that element and exit the function. */
import java.util.*;
public class Solution {
public static int maxFrequencyNumber(int[] arr){
/* Your class should be named Solution
* Don't write main().
* Don't read input, it is passed as function argument.
* Return output and don't print it.
* Taking input and printing output is handled automatically.
*/
HashMap<Integer, Integer> map = new HashMap<>();
for(int i=0; i<arr.length; i++){
if(map.containsKey(arr[i])){
map.put(arr[i], map.get(arr[i])+1);
}else
map.put(arr[i], 1);
}
int maxValue = Integer.MIN_VALUE, maxKey = 0;
for(int i: arr){ //Most imp as we should traverse using array not the hashmap. If u traverse using
if(map.get(i) > maxValue){ //hashmap you will get error
maxValue = map.get(i);
maxKey = i;
}
}
return maxKey;
}
}