Make delicious recipes!

Find majority element in an unsorted array

If the array were sorted, then majority element could be found by a modified binary search in log N time

If its unsorted, then since the majority element occurs n/2+1 times, we can see that its count can not decrease to 0 if we increment count on its occurrence and decrement count on its absence.

So the following code can help us find the majority element:

Note: After finding the probable candidate, another pass is required to ensure that the candidate is indeed majority.
Without this pass, the algo can fail for cases like the following:

Case 1:   5, 6, 6, 7, 8, 9
Case 2:   5, 9, 2, 3

Note 2: The algorithm works only for true majority elements (i.e. whose frequency is greater than or equal to n/2+1 i.e. more than half).
It fails even for cases where frequency is exactly half.
For example, it fails in the following:

Like us on Facebook to remain in touch
with the latest in technology and tutorials!

Got a thought to share or found a
bug in the code?
We'd love to hear from you:

Email: (Your email is not shared with anybody)

Facebook comments:

Site Owner: Sachin Goyal