ACM ICPC Team: Hackerank

This is a hackerank easy question.


You are given a list of N people who are attending ACM-ICPC World
Finals. Each of them are either well versed in a topic or they are
not. Find out the maximum number of topics a 2-person team can know.
And also find out how many teams can know that maximum number of
topics.


Note Suppose a, b, and c are three different people,
then (a,b) and (b,c) are counted as two different
teams.

Input Format


The first line contains two integers, N and M, separated by a single
space, where N represents the number of people, and M represents the
number of topics. N lines follow. Each line contains a binary string
of length M If the i'th line's j'th character is 1, then the i'th
person knows the j'th topic; otherwise, he doesn't know the topic.

Constraints


2≤N≤500

1≤M≤500

Output Format


On the first line, print the maximum number of topics a 2-person team
can know. On the second line, print the number of 2-person teams that
can know the maximum number of topics.

Here is what I wrote:

Scanner console = new Scanner(System.in);
int n = console.nextInt();
int m = console.nextInt();
console.nextLine();
String[] arr = new String[n];
for(int p=0; p>> counts = new HashMap<>();

for(int i = 0; i mapping = new ArrayList<>();
        mapping.add(i+1);
        mapping.add(j+1);

        if(counts.containsKey(count)){
            List> existingMappings = counts.get(count);
            existingMappings.add(mapping);
            counts.put(count, existingMappings);
        }else{
            List> newMappings = new ArrayList<>();
            newMappings.add(mapping);
            counts.put(count, newMappings);
        }

    }
}

int max = counts.keySet().stream().mapToInt(Integer::valueOf).max().orElse(0);

int occurences = counts.get(max).size();

System.out.println(max);
System.out.println(occurences);

This worked and passed the challenge. But it has a code smell: Too many loops a

This part can be optimized a bit, in terms of length.

List mapping = new ArrayList<>();
mapping.add(i+1);
mapping.add(j+1);

if(counts.containsKey(count)){
    List> existingMappings = counts.get(count);
    existingMappings.add(mapping);
    counts.put(count, existingMappings);
}else{
    List> newMappings = new ArrayList<>();
    newMappings.add(mapping);
    counts.put(count, newMappings);
}

Java 8 maps have computeIfAbsent. You can use this to "getOrCreate" the existing mapping like so:

List mapping = new ArrayList<>();
mapping.add(i+1);
mapping.add(j+1);

counts.computeIfAbsent(count, k -> new ArrayList<>()).add(mapping);

Additionally, you do this:

List> existingMappings = counts.get(count);
    existingMappings.add(mapping);
    counts.put(count, existingMappings);

There is no need to put something back into the map when you have retrieved it, because you are retrieving a pointer to a list, and you're using it to add to a list. See this Ideone that lists you put and later retrieve from the map are the same lists.

Okay, so back to this snippet.

List mapping = new ArrayList<>();
mapping.add(i+1);
mapping.add(j+1);

counts.computeIfAbsent(count, k -> new ArrayList<>()).add(mapping);

The new ArrayList constructor can take an initialSize argument. Since you're only going to be adding two integers to the list, you could provide this information and save memory space.

List mapping = new ArrayList<>(2);

Your algorithm could be more optimized - there's no need to count topic knowledge for a team if they know 7 topics together and there's only 6 topics left to check and the top team currently knows 14 topics. Similarily, there's no reason to store how much topics each team knows, only the teams that know the largest amount of topics, and the largest amount of topics you have currently found.

However, I think that when we look at the loops, you can't really get rid of them.

You see, there's two loops needed to make the teams (iterating people over people), and one loop needed to check the topics (iterating over topics). There are clever tricks you could use where you take the binary string and convert it to an integer, but when you do that, you're looping over the characters in the binary string - it has to read the string, after all. You just don't use a for loop.

So we're doomed to have at least 3 loops. What you CAN do is take the counting loop and put it in a separate function. That would "get rid" of one of the loops. Your static analyzer is not built with the idea of such challenges in mind - to see a method with 3 nested loops usually means the method is doing too much work.

StackExchange Code Review Q#160160, answer score: 2