Find majority element in an array given constant external space

Given constant external space (yes no HashMap), how would you improve the following code (code-wise or complexity-wise with stress on the latter) to find the majority element in an array?

/**
 * Created by mona on 5/27/16.
 */

import java.util.Arrays;

public class FinaMajority {
    public static int findMajority(int[] a) {
        Arrays.sort(a);
        int maxCount = Integer.MIN_VALUE;
        int maxIdx = Integer.MIN_VALUE;
        for (int i=0; i maxCount) {
                    maxCount = count;
                    maxIdx = i;
                }
            }
        }
        return a[maxIdx];
    }

    public static void main(String[] args) {
        int[] a = {3,1,2,2,3,2,2,4,4,3,5,2,3,1,3,4,3,3,3};
        System.out.println(findMajority(a));
    }

}

What is a "majority element" ?

It would be good to define this, as there could be multiple interpretations:

• It could be the element that occurs more than any other in the array. This seems the most natural, intuitive interpretation

• It could be the element that occurs more than n / 2 times, as in this online challenge. I think they made a mistake, the common name for this is leader element instead of "majority".

Off-by-one error

The program gives incorrect result for the input [3, 2, 3].
The culprit is here:

int count = 0;
while ( (i+count) < a.length && a[i] == a[i+count]) {
    count++;
    if (count == a.length/2) {
        return a[i];
    }

The sorted array contains [2, 3, 3].
At i=0, since `(i+0)

• increment the count when the same candidate is seen

• decrement the count when a different value is seen

• replace the candidate when the count is 0

Like this:

public int majorityElement(int[] nums) {
    int candidate = 0;
    int count = 0;
    for (int num : nums) {
        if (count == 0) {
            count = 1;
            candidate = num;
        } else if (candidate == num) {
            count++;
            // as a further optimization, you can add a condition here to return early if the required count is reached
        } else {
            count--;
        }
    }
    return candidate;
}

This works when the leader element is guaranteed to exist.
If it's not guaranteed to exist,
then you need another \$O(n)\$ pass to verify the count of the candidate is indeed greater than half of the number of all elements.

StackExchange Code Review Q#129529, answer score: 3