Majority - facebook code lab - optimal solution

July 18, 2016

Problem statement:

Given an array of size n, find the majority element. The majority element is the element that appears more than floor(n/2) times.

You may assume that the array is non-empty and the majority element always exist in the array.

Example :

Input : [2, 1, 2]
Return  : 2 which occurs 2 times which is greater than 3/2. 

Think about brute force solution first,
sort the array first, and then, medium of the array is the majority element. And the time complexity is O(nlogn).
If the size of the array is even, then, medium is two nodes in the center. And if the size of the array is odd, the medium is the middle one.

Spent 10 -15 minutes to find the optimal solution, beat the time complexity O(nlogn). The array does not need to be sorted, try to think about the partition of the array, pivot value - how to find the one?

No progress in over 15 minutes. Then, read the hint from the facebook code lab.

Optimal solution idea:
Just try to go through the array once, and set the majority element, and keep the count of majority element.

Really like the hint from facebook code lab:
If two distinct elements are removed from the array, the majority element is still the same one in the array.


1st practice:
https://gist.github.com/jianminchen/c6f01498a6de4ca2df3d813b375a3d6d

Study the code provided by facebook code lab:
https://gist.github.com/jianminchen/7406702476e8fe7b58934fccb9a4e674

The code is much simple and short.
Julia wrote ugly if statement for 4 cases, but the editorial solution only has one if statement. How does that happen?

The reasoning is more stronger  one step further, if the count is 0 for majority element, then just set last one as majority element and count = 1. No candidate, and then, set the last one as the candidate. There is no worry about it. But make the code more simple, not too much if statement.