Majority Element

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

Example:

Input: [5,5,1,1,3,5,5]
Output: 2

Approach: Using Boyer–Moore majority vote algorithm. We can do it by sorting the array or using hash but majority vote algorithm do it most efficiently in terms of time and space.

Implementation in C#:

    public int MajorityElement(int[] nums)

    {

        int length = nums?.Length ?? 0;

        if (length == 0)

        {

            return int.MinValue;

        }

        int count = 1;

        int majElement = nums[0];

        for (int i = 1; i < length; ++i)

        {

            majElement = count == 0 ? nums[i] : majElement;

            count = majElement == nums[i] ? count + 1 : count - 1;

        }

        count = 0;

        for (int i = 0; i < length; ++i)

        {

            if (majElement == nums[i])

            {

                ++count;

            }

        }

        return count > length / 2 ? majElement : int.MinValue;

    }

Complexity: O(n)