Voting Algorithm

Question

Find the element the occurs more than \$\dfrac{n}{2}\$ times in an input array, where \$n\$ is input array length.

I'm looking for code review, optimizations and best practices.

  public final class VotingAlgorithm {

    // non-instantiable.
    private VotingAlgorithm() {} 

    /**
     * Returns the number which occurs more than n/2 times.
     * If such a number does not exist, then results are unpredicatable.
     * 
     * @param a     the input array
     * @return      the number occuring more than n/2 times.
     */
    public static int maxElement(int[] a) {
        int maxElementIndex = 0;
        int counter = 1;

        for (int i = 1; i < a.length; i++) {
            if (a[maxElementIndex] == a[i]) {
                counter++;
            } else {
                counter--;
            }
            if (counter == 0) {
                maxElementIndex = i;
                counter++;
            }
        }
        return a[maxElementIndex];
    }


    public static void main(String[] args) {
        int[] a1 = {1, 2, 3, 1, 1, 1};
        assertEquals(1, maxElement(a1));

        int[] a2 = {2, 3, 1, 1, 1, 1};
        assertEquals(1, maxElement(a2));

        int[] a3 = {1, 1, 1, 1, 2, 3};
        assertEquals(1, maxElement(a3));

        int[] a4 = {1, 2, 1, 3, 1, 1};
        assertEquals(1, maxElement(a4));

        int[] a5 = {1, 2, 3, 4, 1, 1, 1};
        assertEquals(1, maxElement(a5));

        int[] a6 = {2, 3, 4, 1, 1, 1, 1};
        assertEquals(1, maxElement(a6));

        int[] a7 = {1, 1, 1, 1, 2, 3, 4};
        assertEquals(1, maxElement(a7));

        int[] a8 = {1, 2, 1, 3, 1, 4, 1};
        assertEquals(1, maxElement(a8));
    }
}

Answer 1

Your code is very clever, perhaps a little too clever... It almost looks like you wrote the code first, and then asked yourself - what can this achieve?
As @rolfl said - as it is currently written - the code is all but useless, because most of the time the result is unpredictable. Calling this method will return a value, which could either have more than half the length of occurrences, or... not?

You could achieve at least as much information with the same complexity, by keeping more complete score.

Here is an example, where you can save the count of each element, and keep the one with most occurrences:

public int elementWithMostOccurrences(int[] inputArray) {

    HashMap<Integer, Integer> occurrenceCount = new HashMap<Integer, Integer>();
    int currentMaxElement = inputArray[0];

    for (int i = 1; i < inputArray.length; i++) {
        Integer elementCount = occurrenceCount.get(inputArray[i]);
        if (elementCount != null)) {
            occurrenceCount.put(inputArray[i], elementCount + 1);
            if (elementCount >= occurrenceCount.get(currentMaxElement)) {
                currentMaxElement = inputArray[i];
            }
        } else {
            occurrenceCount.put(inputArray[i], 1);
        }
    }

    // if you want to return the element only if it has more than half the array size you can:
    // if (occurrenceCount.get(currentMaxElement) > inputArray.Length / 2) { ... }

    return currentMaxElement;
}

This example is also \$O(n)\$ complexity, but gives a valuable result every time.

Answer 2

The JavaDoc and the method names do not agree.

The method name maxElement implies the method will get either:

1. the element that occurs most frequenly
2. the element with the largest value

This function may, or may not, do both.

The JavaDoc indicates that this function will return the value that occurs more more than half-the-time, and that if there is no such element, the result is undefined.

This makes the method useless, because anyone calling the method will then have to re-scan the entire data set to see whether the method is returning a right answer, or an undefined answer.

Since repeating all the work to check whether the method produced a reliable result or not is required anyway, you may as well do it in the method itself, and then return a result which removes the non-determinism.