[Amazon] Majority Element II

Problem: This problem is similar to the previous problem of finding Majority element in the array but here we are trying to find all elements that appear more than n/3 times instead of n/2 elements.

Example:

Input: nums = [6,3,6,5]
Output: [6]

Approach: We are going to use Boyer–Moore majority vote algorithm like we used in previous problem. Important thing here is to consider is like in case of previous problem there could be only one element which can appear more than n/2 times, in this problem there can be maximum two elements which can appear more than n/3 times. Here is the proof:

Say two elements occurred n/3 + num1 and n/3 + num2 times so the total number of times these two elements appeared in array is:

n/3 + num1 + n/3 + num2 = 2n/3 + num1 + num2 

Now you see the third number could appear maximum -

n - (2n/3 + num1 + num2) = n/3 - num1 - num2 

So you can see there can't be a third number which can occur more than n/3 times.

Implementation in C#:

    public IList<int> MajorityElement(int[] nums)

    {

        int length = nums?.Length ?? 0;

        if (length == 0)

        {

            return new List<int>();

        }

        int firstMajor = nums[0];

        int secondMajor = int.MaxValue;

        int count1 = 1, count2 = 0;

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

        {

            if (nums[i] == firstMajor)

            {

                ++count1;

            }

            else if (nums[i] == secondMajor)

            {

                ++count2;

            }

            else if (count1 == 0)

            {

                firstMajor = nums[i];

                count1 = 1;

            }

            else if (count2 == 0)

            {

                secondMajor = nums[i];

                count2 = 1;

            }

            else

            {

                --count1;

                --count2;

            }

        }

        count1 = 0;

        count2 = 0;

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

        {

            if (nums[i] == firstMajor)

            {

                ++count1;

            }

            else if (nums[i] == secondMajor)

            {

                ++count2;

            }

        }

        var result = new List<int>();

        if (count1 > length / 3)

        {

            result.Add(firstMajor);

        }

        if (count2 > length / 3)

        {

            result.Add(secondMajor);

        }

        return result;

    }

Complexity: O(n)