Leetcode 229 Solution

This article provides solution to leetcode question 229 (majority-element-ii)
Categories:
Tags:
Access this page by simply typing in "lcs 229" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/majority-element-ii

Solution

class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {
        int m = 0;
        int n = 0;
        int cm = 0;
        int cn = 0;

        for (auto &num : nums)
        {
            if (num == m)
                cm++;
            else if (num == n)
                cn++;
            else if (cm == 0)
                m = num, cm = 1;
            else if (cn == 0)
                n = num, cn = 1;
            else
                cm--, cn--;
        }

        cm = 0;
        cn = 0;

        for (auto &num : nums)
        {
            if (m == num)
                cm++;
            else if (n == num)
                cn++;
        }

        vector<int> res;

        if (cm != 0 && cm > nums.size() / 3)
            res.push_back(m);

        if (cn != 0 && cn > nums.size() / 3)
            res.push_back(n);

        return res;
    }
};