2D Array, best average calculator using HashMap

Question

Problem Statement: I have a 2D array of strings containing student names and respective marks as below

String[][] scores = {{"Bob","85"},{"Mark","100"},{"Charles","63"},{"Mark","34"}};

I want to calculate the best average among all the students available, i.e with the above input the best average should be 85.

My Attempt: I tried to solve this using HashMap as below.

public int  bestAverageCalculator(String[][] scores) {

    // This HashMap maps student name to their list of scores
    Map<String,List<Integer>> scoreMap = new HashMap<String,List<Integer>>();
    for(String[] score:scores) {
        String name = score[0];
        int currentScore =Integer.parseInt(score[1]);

        if(scoreMap.containsKey(name)) {
            List<Integer> scoreList = scoreMap.get(name);
            scoreList.add(currentScore);
            scoreMap.put(name, scoreList);
        }
        else {
            List<Integer> scoreList = new ArrayList<Integer>();
            scoreList.add(currentScore);
            scoreMap.put(name, scoreList);
        }
    }
    //scoreMap will be {Charles=[63], Bob=[85], Mark=[100, 34]}
    //After Map is formed i am iterating though all the values and finding the best average as below
    int bestAverage = 0;
    for(List<Integer> value:scoreMap.values()) {
        int sum = 0;
        int count = 0;
        for(int i:value) {
            sum+=i;
            count++;
        }
        int average = (int)Math.floor(sum/count);
        if(average>bestAverage)
            bestAverage = average;
    }

    return bestAverage;// returns 85

}

The implementation is correct and i am getting the answer as expected, but i was told the space complexity of the program is more and it can be achieved without using the List<Integer> for marks, i am not able to understand how average can be calculated on fly without storing list of marks.

Please suggest if any other methods can solve this other than HashMap.

Any help would be appreciated.

Answer 1

You could store for each student a constant amount of data :

1. the student's name
2. the sum of all the student's marks
3. the number of the student's marks

This will make the space complexity O(m) where m is the number of unique students (instead of your O(n) where n is the number of marks).

For example, you can have a Student class with these 3 properties (and store the data in a List<Student>), or you can have a Map<String,int[]> with the key being the student's name and the value being an array of two elements containing the sum of the marks and the number of marks.

You can construct this data while iterating over the input.

Now you can compute the average for each student and find the highest average.