Majority Element

The majority element is the element that appears more than ⌊size/2⌋ times.

Let's see several examples.

If the input array is [1, 1, 3], the majority item is 1 because it occurs 2 times and it's more than 3/2 (where 3 - array size). so 1 - the majority element.

If the input array is [1, 1, 3, 3, 4, 3], the majority element is 3 because it occurs 3 times and it equals 6/2 (where 6 - array size). So 3 - the majority element. All other elements occur less than 6/2.

Algorithm

There are several ways how to find a majority element in an array.

Using a dictionary or HashMap

The goal is to store each element's frequency in the dictionary and return the element if its frequency becomes more than array size/2. The time complexity of this algorithm is O(n). The algorithm requires O(n) space to store elements. It's a working algorithm, but it could be done better.

Boyer–Moore Majority Vote Algorithm

Using this algorithm, we can find a majority element in linear time and constant space. The main idea is to count the majority element occurrence while traversing an array.

• In the beginning, the algorithm sets the first array element a majority element
• During traversing an array, we count the majority element occurrence.
  • If we see the sameelement as the majority element, we incrementthe count.
  • If we see a different element, we decrement the count.
    • if the count is less than zero, we set a current element as a new majority element.

Code

    public int MajorityItem(int[] array)
    {
        if (array == null || array.Length == 0)
        {
            return -1;
        }

        if (array.Length == 1)
        {
            return array[0];
        }

        int count = 1;
        int result = array[0];

        for (int i = 1; i < array.Length; i++)
        {
            if (array[i] == result)
            {
                count++;
            }
            else
            {
                count--;
                if (count == 0)
                {
                    result = array[i];
                    count = 1;
                }
            }
        }

        return result;
    }

Time Complexity: O(n)