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&lt;n; p++){
    String s = console.nextLine();
    arr[p] = s;
}


Map&lt;Integer, List&lt;List&lt;Integer&gt;&gt;&gt; counts = new HashMap&lt;&gt;();

for(int i = 0; i&lt; n-1; i++){

    String str=arr[i];

    for(int j=i+1; j&lt;n; j++){


        String secondStr = arr[j];

        int count = 0;
        for(int k=0; k&lt;m; k++){

            if(str.charAt(k) == '1' || secondStr.charAt(k) == '1'){
                count ++;
            }

        }

        List&lt;Integer&gt; mapping = new ArrayList&lt;&gt;();
        mapping.add(i+1);
        mapping.add(j+1);

        if(counts.containsKey(count)){
            List&lt;List&lt;Integer&gt;&gt; existingMappings = counts.get(count);
            existingMappings.add(mapping);
            counts.put(count, existingMappings);
        }else{
            List&lt;List&lt;Integer&gt;&gt; newMappings = new ArrayList&lt;&gt;();
            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 and even inner loops. Any improvements?
This part can be optimized a bit, in terms of length.

List&lt;Integer&gt; mapping = new ArrayList&lt;&gt;();
mapping.add(i+1);
mapping.add(j+1);

if(counts.containsKey(count)){
    List&lt;List&lt;Integer&gt;&gt; existingMappings = counts.get(count);
    existingMappings.add(mapping);
    counts.put(count, existingMappings);
}else{
    List&lt;List&lt;Integer&gt;&gt; newMappings = new ArrayList&lt;&gt;();
    newMappings.add(mapping);
    counts.put(count, newMappings);
}


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

List&lt;Integer&gt; mapping = new ArrayList&lt;&gt;();
mapping.add(i+1);
mapping.add(j+1);

counts.computeIfAbsent(count, k -&gt; new ArrayList&lt;&gt;()).add(mapping);


Additionally, you do this:

    List&lt;List&lt;Integer&gt;&gt; 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&lt;Integer&gt; mapping = new ArrayList&lt;&gt;();
mapping.add(i+1);
mapping.add(j+1);

counts.computeIfAbsent(count, k -&gt; new ArrayList&lt;&gt;()).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&lt;Integer&gt; mapping = new ArrayList&lt;&gt;(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.