Most Occurred Integer in the List

Problem:

You are given a list of integers and you need to find the most occurred integer or sometime it is called most popular element in the list.

 static Integer[] intList = {5,21,21,3,4,5,5,3,6,7,65,5,21,21,21,4,4,4,4,4,4,4,4,4,4};  

This is very common interview question and can have multiple correct solution, but interviewer expect you to give the most efficient solution.

One solution would be to

1. Iterate through the list twice 
2. Compare the elements inside the second iteration
3. Increment the counter.
4. Compare the counter with previously saved maxOccurred variable.
5. And if counter is greater than previous value, save the counter value to maxOccurred variable.

1:       public static void mostOccurentElement(){  
2:            Integer mostOccurentElement=0;  
3:            Integer mostOccurences = 0;  
4:            for (Integer number : intList) {  
5:                 int count = 0;  
6:                 for (Integer number2 : intList) {  
7:                      if(number.equals(number2)){  
8:                           count++;  
9:                      }   
10:                 }  
11:                 if(count > mostOccurences){  
12:                      mostOccurences = count;  
13:                      mostOccurentElement = number;  
14:                 }  
15:            }  
16:            System.out.println("Most Occured element = "+mostOccurentElement+" Most occurnces are : "+mostOccurences);  
17:       }  

Output of above solution:
Most Occurred element = 4 Most occurrences are : 11

Complexity of this method is O(N²) where N is length of this list. Better solution would be to avoid the second for loop. Second solution would be:

1. Iterate through the list once.
2. Get and populate the value as number of occurrences of each element into the map.
3. Iterate through the map 
4. Compare each value with previously saved maxOccurred variable.
5. And if value is greater than previous value, save the counter value to maxOccurred variable.

1:       public static void mostOccurentElementByMap(){  
2:            Map<Integer, Integer> map = new HashMap<Integer, Integer>();  
3:            Integer mostOccurentElement=0;  
4:            Integer mostOccurences = 0;  
5:            for (Integer number : intList) {  
6:                 if(map.containsKey(number)){  
7:                      Integer integer = map.get(number);  
8:                      map.put(number, integer+1);  
9:                 } else {  
10:                      map.put(number, 1);  
11:                 }  
12:            }  
13:            Set<Entry<Integer, Integer>> entrySet = map.entrySet();  
14:            for (Entry<Integer, Integer> entry : entrySet) {  
15:                 if(mostOccurences < entry.getValue()){  
16:                      mostOccurences = entry.getValue();  
17:                      mostOccurentElement = entry.getKey();  
18:                 }  
19:            }  
20:            System.out.println("Most Occured element = "+mostOccurentElement+" Most occurnces are : "+mostOccurences);  
21:       }  

Output of above solution:
Most Occurred element = 4 Most occurrences are : 11

Complexity of this method is O(N) where N is length of this list. The space complexity is also N. I will add new better solution if I could also reduce the space complexity. If anyone of you have better solution, please do suggest in comment section.