229 Majority Element II

Given an integer array of size n, find all elements that appear more than $$\floor{\frac{n}{3}} \newcommand{\floor}[1]{\lfloor #1 \rfloor}$$ times. The algorithm should run in linear time and in O(1) space.

• Hint: How many majority elements could it possibly have?

Solution:

class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {
        vector<int> res;
        int n = nums.size();
        if ( n <= 1 ) return nums;
        // there are at most 2 majority elements
        int icount1 = 1, curr1 = nums[0], i = 1;
        int icount2 = 0, curr2 = MAX_INT;
        while ( i <= n-1 ) {
            if ( icount1 == 0 and nums[i] != curr2 ) {
                curr1 = nums[i++];
                icount1 = 1; continue;
            }
            if ( icount2 == 0 and nums[i] != curr1 ) {
                curr2 = nums[i++];
                icount2 = 1; continue;
            }
            if ( nums[i] == curr1 ) { icount1 += 1; i += 1; continue;}
            if ( nums[i] == curr2 ) { icount2 += 1; i += 1; continue;}
            if ( nums[i] != curr1 and nums[i] != curr2 ) {
                icount1 -= 1;
                icount2 -= 1;
                i += 1; continue;
            }
        }
        icount1 = 0;
        icount2 = 0;
        for ( i = 0; i <= n-1; i++ ) {
            if ( nums[i] == curr1 ) icount1 += 1;
            if ( nums[i] == curr2 ) icount2 += 1;
        }
        if ( curr1 == curr2 ) {
            if ( (icount1 + icount2) >= n/3 + 1 ) res.push_back(curr1);
        }
        else {
            if ( icount1 >= n/3 + 1 ) res.push_back(curr1);
            if ( icount2 >= n/3 + 1 ) res.push_back(curr2);
        }
        return res;
    }
};

Notes:
The algorithm is similar to $$\floor{\frac{n}{2}} \newcommand{\floor}[1]{\lfloor #1 \rfloor}$$ problem, but now we keep track of two possible candidates: curr1 and curr2. (There are at most two majority elements in a given array.)

• Note the special case when curr1 == curr2 after the first scan. (Do not return duplicate elements in the result.)