Most Recurrent Number in List using HashMap

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!