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:
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
- We first encounter
A and we remember that A has been encountered 1 time.
- Then we move to
B. B was never encountered so we also remember that, now, we encoutered it 1 time.
- 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.
- 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();
}
