# Most Recurrent Number in List using HashMap

by Bittle in Dynamic Programming

Problem:

Find the most recurrent number in the list, then print the value and times it was repeated.

Examples:

input: {1, 3, 3}

output: KEY = 3, REPEATED = 2

input: {1, 2, 3, 1, 4, 5, 6, 4, 3, 4, 4, 4, 4, 9, 8, 6, 8, 7}

output: KEY = 4, REPEATED = 6

Solution (in java):

``````import java.util.HashMap;

public class MostRecurrent {

private static void solve(int[] arr) {
if (arr.length == 0) {
System.out.println("Empty list");
// return; gets out of (finalizes) the method
return;
}

HashMap<Integer, Integer> map = new HashMap<>();

// loop through arr and add to map
for (int a : arr) {
if (map.containsKey(a)) {
// seen before, increment by 1
map.put(a, map.get(a) + 1);
} else {
// first time seeing, put 1
map.put(a, 1);
}
}

// now loop through the list again, but comparing recurrences
int key = 0;
int repeat = -1;
for (int a : arr) {
int value = map.get(a);
if (value > repeat) {
key = a;
repeat = value;
}
}

System.out.println("KEY = " + key + ", REPEATED = " + repeat);
}

public static void main(String[] args) {
int[] arr = {1, 2, 3, 1, 4, 5, 6, 4, 3, 4, 4, 4, 4, 9, 8, 6, 8, 7};
solve(arr);
}
}
``````

output:

``````KEY = 4, REPEATED = 6
``````

The big O runtime of the algorithm is O(n):

1. First loop iterates through the input and inserts into the HashMap
2. Second loop iterates through the input and accesses HashMap data
• HashMap insertions and lookup runtimes are constant O(1)
• O(n * 1)+(n * 1) = O(2n) = O(n)

Comment below if you have any questions!