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&lt;a.length; i++) {
            int count = 0;
            while ( (i+count) &lt; a.length &amp;&amp; a[i] == a[i+count]) {
                count++;
                if (count == a.length/2) {
                    return a[i];
                }
                if (count &gt; 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) &lt; a.length &amp;&amp; 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) &lt; a.length and a[i] == a[i+0],
count is incremented to 1 on the next line,
and since a.length/2 is 1, the method prematurely returns 2.

The fix is to move count++ to the end of the while loop.

Notice that starting from count = 0 is pointless.
It would be better to start from count = 1.

Index out of bounds for singleton array

The program will crash for the input [1].
In this case maxIdx will never change,
its value remains at Integer.MIN_VALUE,
and so it will crash on the line return a[maxIdx].

Slowness

The program is too slow for large arrays, because after counting the consecutive numbers,
it does not skip those,
and continues checking from the next value of i.
Due to this, the time complexity of the loop degenerates to \$O(n^2)\$.

You can improve by adding to i the number of elements that can be skipped.

int count = 1;
while ((i + count) &lt; a.length &amp;&amp; a[i] == a[i + count]) {
    if (count == a.length / 2) {
        return a[i];
    }
    if (count &gt; maxCount) {
        maxCount = count;
        maxIdx = i;
    }
    count++;
}
i += count - 1;


Alternative implementation

If you're really looking for the majority element and not the leader element, then your implementation can be written slightly simpler without a nested loop:

public int findMajority(int[] nums) {
    Arrays.sort(nums);

    int maxCount = 0;
    int maxIndex = 0;

    int count = 1;

    for (int i = 1; i &lt; nums.length; i++) {
        if (nums[i - 1] == nums[i]) {
            count++;
            if (count &gt; maxCount) {
                maxIndex = i;
                maxCount = count;
            }
        } else {
            count = 1;
        }
    }
    return nums[maxIndex];
}


Finding the leader element

If you're actually looking for the leader element,
the element that occurs more than n / 2 times,
then an \$O(n)\$ solution is possible:


track a candidate and its count
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.