Finding the candidate with the majority of ballots

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 listOfBallots) {
         int totalSize = listOfBallots.size();
         count = listOfBallots.size()/2;
         if (listOfBallots.isEmpty() == true){
             return null;
         } else {
             for (int i = 0; i  count){
                     count = running;
                     winner = current;
                 }
             }
         }
         if (count > (listOfBallots.size()/2)){
             return winner;
         } else {
             return null;
         }

     }
}

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 (starting with Java 8).

Putting it all together

We all those comments, you could have the following:

public static String getWinner(final List 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

• We first encounter A and we remember that

StackExchange Code Review Q#126522, answer score: 27