5
\$\begingroup\$

I am doing a code wars problem and so far I have managed to loop through a collection to find the "winner" (defined by the String that appears more than collection.size()/2). However, my code times out and isn't efficient enough. How can I make this more efficient?

import java.util.List;

public class BallotsCounter1 {
    static String winner;
    static String current;
    static int count;

     public static String getWinner(final List<String> listOfBallots) {
         int totalSize = listOfBallots.size();
         count = listOfBallots.size()/2;
         if (listOfBallots.isEmpty() == true){
             return null;
         } else {
             for (int i = 0; i < listOfBallots.size(); i++){
                 int running = 0;
                 current = listOfBallots.get(i);
                 for (int j = 0; j < listOfBallots.size(); j++){
                     if (listOfBallots.get(i) == listOfBallots.get(j)){
                         running++;
                     }
                 }
                 if (running > count){
                     count = running;
                     winner = current;
                 }
             }
         }
         if (count > (listOfBallots.size()/2)){
             return winner;
         } else {
             return null;
         }


     }
}
\$\endgroup\$
27
\$\begingroup\$

Before making it faster, it is important to make it better.


Scope of variables

You currently have 3 static variables in your code

static String winner;
static String current;
static int count;

that are only used inside the getWinner method. This is not a good idea:

  • A variable should have a scope as minimal as possible. This means you only declare that variable when you need it and not a moment before.
  • They are not private which means that another unrelated class could even access and modify them, thereby completely destroying the algorithm.

You should remove those static variables and have instead:

int count = listOfBallots.size()/2;
// ...
String current = listOfBallots.get(i);
// ...
String winner = null; // before the if/else part

Unused variable

You are storing the size of the input list into the variable totalSize but this variable is unused in the rest of your code. You should either remove it (unused code should be deleted) or make use of it and not call listOfBallots.size() each time it is needed.

Since the current code gets the size of the list multiple times, it would be better to store it like you did and reuse that variable. Example, instead of:

int count = listOfBallots.size()/2;

have

int count = totalSize / 2;

Also, notice the added spaces before the operator / that adds to readability.

Don't compare booleans to true or false

In the case of an empty list, you currently return null with:

if (listOfBallots.isEmpty() == true){
    return null;
}

This explicit check with == true is redundant and even harder to read than a simple

if (listOfBallots.isEmpty()) {
    return null;
}

Early return

In your code, you are returning early in the case of an empty list. But you are not going all the way. You have:

if (listOfBallots.isEmpty()) {
    return null;
} else {
    // ...
}

The else part is not needed and it adds an unnecessary indent to the code. Consider removing it, thereby shifting all the subsequence code one indentation to the left, so making it easier to read for small screens:

if (listOfBallots.isEmpty()) {
    return null;
}
// ...

As noted by Fabian Barney in the comments, you don't even need to return early: when the list is empty, your initial count will be equal to listOfBallots.size()/2 and null will still be returned. Might as well get rid of it and make the code shorter.

Enhanced for loop

Your two loops are written using the traditional index solution:

for (int i = 0; i < totalSize; i++){
    // ...
    String current = listOfBallots.get(i);
    for (int j = 0; j < totalSize; j++){
        if (listOfBallots.get(i) == listOfBallots.get(j)){
            // ...

When you don't need the index, it is better to use the enhanced for loop. It makes the code more compact and easier to read:

for (String current : listOfBallots) {
    // ...
    for (String other : listOfBallots) {
        if (current == other) {

Notice that it also makes another problem appear more clearly:

Do not compare Strings with ==

This won't work like you would expect. To compare Strings, you should really use the equals method and have:

if (current.equals(other))

Returning null

As a last comment, if you explicitely return null when no winner has been found then it would be best to document it clearly. There could be other approaches, like:

  • Throwing a custom exception.
  • Returning an Optional<String> (starting with Java 8).

Putting it all together

We all those comments, you could have the following:

public static String getWinner(final List<String> listOfBallots) {
    int totalSize = listOfBallots.size();
    int count = totalSize / 2;
    String winner = null;
    for (String current : listOfBallots) {
        int running = 0;
        for (String other : listOfBallots) {
            if (current.equals(other)) {
                running++;
            }
        }
        if (running > count) {
            count = running;
            winner = current;
        }
    }
    if (count > totalSize / 2) {
        return winner;
    } else {
        return null;
    }
}

Now, let's analyze your current code and spot where the slowness is coming from. The goal of the method is:

to find the "winner" (defined by the String that appears more than collection.size()/2).

To do that, you are looping over the list, and for each element, you are looping a second time over the list and counting equals element. That is the slow part: for a list of size n, you just made your approach O(n2). You are traversing the list again and again to find the equal elements.

How to improve that? Look at it this way: the goal is to count the number of times the String appears in the list. To do that, we just need to loop over that list only once, but remember the current count.

Take the following list:

A  ---  B  ---  A  ---  D
  1. We first encounter A and we remember that A has been encountered 1 time.
  2. Then we move to B. B was never encountered so we also remember that, now, we encoutered it 1 time.
  3. Then we move to A. But, now, we know that it has already been encoutered 1 time: we remembered it already. So we can just remember that A was encoutered 2 times now.
  4. Finally, we hit D that we never encountered and we remember that we encoutered it 1 time.

In that pattern, the list was only traversed a single time. With the current implementation, it would have been traversed 5 times (the main one and 4 other times to count for how many times each element appeared).

A good data structure to use for that memory is a Map<String, Integer>, that is to say a data structure that maps one String into a count.

There is another optimization that we can make. The winner is the String appearing more than half the time in the initial collection. This means that once we found the winner, there is no need to continue. No other element will be able to appear more than the element that appeared more than half the time. Put another way, if a String A has appeared more than n/2 times, no other element B can appear more times than A: there are less than n/2 elements remaining.

With all this in mind, this is what you could have, that will be a lot more performant:

public static String getWinner(final List<String> listOfBallots) {
    int count = listOfBallots.size() / 2;
    Map<String, Integer> map = new HashMap<>();
    for (String current : listOfBallots) {
        int running = map.containsKey(current) ? map.get(current) + 1 : 1;
        map.put(current, running);
        if (running > count) {
            return current;
        }
    }
    return null;
}

For each element, we determine the number of times it appeared: if it already appeared (so the map contains the key), we add 1; else it is the first time.

Then when we found an element that appeared more than half the time, we return it directly.

With Java 8 constructs

Using Java 8, it is possible to use the merge method on the map and simplify a bit the code. Instead of having

int running = map.containsKey(current) ? map.get(current) + 1 : 1;
map.put(current, running);

we could just have:

int running = map.merge(current, 1, Integer::sum);

And if you're using Java 8, consider returning an Optional<String> instead of null:

public static Optional<String> getWinner(final List<String> listOfBallots) {
    int count = listOfBallots.size() / 2;
    Map<String, Integer> map = new HashMap<>();
    for (String current : listOfBallots) {
        int running = map.merge(current, 1, Integer::sum);
        if (running > count) {
            return Optional.of(current);
        }
    }
    return Optional.empty();
}
\$\endgroup\$
  • 3
    \$\begingroup\$ Exhaustive!! +1 \$\endgroup\$ – Insane Apr 23 '16 at 17:42
  • 2
    \$\begingroup\$ @FabianBarney Yes, you're right, it is not needed. Thanks for your comment! I edited with that. \$\endgroup\$ – Tunaki Apr 23 '16 at 17:56
  • 1
    \$\begingroup\$ @Tunaki this was very informative and I appreciate your attention to detail. I am new to Java and this was a fantastic mini-lesson. I really appreciate it. Thank you. \$\endgroup\$ – Archeofuturist Apr 23 '16 at 18:30
  • 1
    \$\begingroup\$ Answers like this are why this site exists. There's something beautiful about seeing clean, succinct, code coming out of a veritable mess! The only meaningful thing missing from the answer is a mention of unit testing. \$\endgroup\$ – Boris the Spider Apr 24 '16 at 11:19
  • 1
    \$\begingroup\$ @SimonAugustus - Note that most of this advice is not Java-specific (except the Java 8 stuff at the end, though many languages have equivalents), and will work with most OOP (or just C-style in general) languages as well. So if you find yourself working in C++ or C# or whatnot, the same tips still apply. \$\endgroup\$ – Darrel Hoffman Apr 24 '16 at 15:50
3
\$\begingroup\$

Two problems stand out to me.

The first minor issue is that you have a special case for an empty list. It's not necessary. Special cases clutter the code, and add codepaths which need to be verified. (If your algorithm didn't work in the general case, then that would be a sign that the algorithm might be wrong.)

The more fundamental issue is that your algorithm is O(n2), which is bad news for performance. The Boyer-Moore majority vote algorithm can do the job in O(n) time and O(1) space.

\$\endgroup\$
0
\$\begingroup\$

+1 to @Tunaki for his very good and exhaustive answer.

Another option would be to sort your list (O(logN)) and run through it counting the longest streak (O(N)):

A B C C B D C A D unsorted

A A B B C C C D D sorted

Longest streak is 3 C.

Of course, you can stop earlier when you determine the current streak if enough (i.e. more than half the size of your list).

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.