Creating List of String elements that occur a certain amount of times using only the List ADT I am tasked with creating a list with no duplicates of all String elements, in this case first names, of an ArrayList. The method is passed a threshold, and the method must store the first name if it has occurred at least the amount of the threshold. The restriction is that I am only allowed to use the List ADT. I have this code storing it in a ArrayList and it works, but I am worried about the algorithmic complexity which seems to be \$O(n^2)\$ as a worst case. Is there a more efficient way of writing this method?

static List&lt;String&gt; commonFirstNames(ArrayList&lt;Student&gt; students, int threshold) {
    ArrayList&lt;String&gt; results = new ArrayList&lt;String&gt;();

    String[] nameArray;
    String firstName;
    int counter = 0;
    for (int i = 0; i &lt; students.size(); i++) {
        nameArray = students.get(i).getName().split(" ");
        firstName = nameArray[0];

        boolean isInResults = results.contains(firstName);
        if (!isInResults) {
            for (int j = i; j &lt; students.size(); j++) {
                String[] otherNameArray = students.get(j).getName().split(" ");
                String otherFirstName = otherNameArray[0];

                if (otherFirstName.equals(firstName)) {
                    counter++;
                }
            }
            if (counter &gt;= threshold) {
                results.add(firstName);
            }
        }
            counter = 0; 
    }

    return results;
}
This is more of a hint but unfortunately I cannot comment on your post.

As greybeard already mentioned, you could sort the List and then count the elements with equal firstName. A representation of the sorted List may give you an idea how to implement this:

List("Alice A", "Alice B", "Alice C", "Brian A", "Brian B", "Jason A", "Jason B", "Jason C", ...)


Another solution is to use a Collection that counts equal entries.

This Collection implementation is often available as Bag. This is unfortunately not included in the Java standard library, but implementations are available in Apache Commons. Note that you have to transform the List of firstName + lastName to a list that only contains the firstName. You can use a Transformer also available in Apache Commons that strips the lastName (the values of the resulting List will then be lazy evaluated).