<p>Given an integer array of size <code>n</code>, find all elements that appear more than <code>&lfloor; n/3 &rfloor;</code> times.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [3,2,3]
<strong>Output:</strong> [3]
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [1]
<strong>Output:</strong> [1]
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,2]
<strong>Output:</strong> [1,2]
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 5 * 10<sup>4</sup></code></li>
	<li><code>-10<sup>9</sup> &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>
</ul>

<p>&nbsp;</p>
<p><strong>Follow up:</strong> Could you solve the problem in linear time and in <code>O(1)</code> space?</p>

class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {
        int n = nums.size();
        int m1 = INT_MIN;
        int m2 = INT_MIN;
        int f1 = 0,  f2 = 0;
        vector<int> ans;
        for(int x : nums)
        {
            if( f1  == 0 && x != m2)
            {
                m1 = x;
                f1++;
            }
            else if(f2 == 0 && x != m1)
            {
                f2++;
                m2 = x;
            }
            else if(x == m1) f1++;
            else if(x == m2) f2++;
            else
            {
                f1--;
                f2--;
            }
        }
        int cnt1 = 0, cnt2 = 0;
        for (int x : nums) {
            if (x == m1) cnt1++;
            if (x == m2) cnt2++;
        }
        int mini = int(n / 3) + 1;
        if (cnt1 >= mini) ans.push_back(m1);
        if (cnt2 >= mini) ans.push_back(m2);
        return ans;
        // I haven't coded the O(1) solution yet.

        // initially, I was mistaking this for asking the top 3 elements. NO!
        // it is just asking for values with freq. above n/3.

        // o(N) space : frequency map
        // us map se heap of pair of integers -- NO! you have it wrong!
        // it is asking for values with frequency above a threshold. Not the top 3 elements.
        // it just so happens that the max no. of values that can have a frequency above 
        // n/3 are 2.
        // so we could have a maximum of 2 values in our answer list.(and at minimum, 0 
        // values.)
    }
};
18600