16-Majority Element - II

#include <bits/stdc++.h>

vector<int> majorityElementII(vector<int> &arr)
{
    // Write your code here.
    // int n=arr.size();
    // vector<int> ans;
    // unordered_map<int,int> mp;
    // for(int i=0;i<arr.size();i++){
    //     mp[arr[i]]++;
    // }

    // for(auto i:mp){
    //     if(i.second > n/3){
    //         ans.push_back(i.first);
    //     }
    // }
    // return ans;

    //Optimal Approch
    int n=arr.size();
    int cnt1=0,cnt2=0;
    int el1=INT_MIN;
    int el2=INT_MIN;

    for(int i=0;i<n;i++){
        if(cnt1==0 && el2 != arr[i]){
            cnt1=1;
            el1=arr[i];
        }
        else if(cnt2==0 && el1 != arr[i]){
            cnt2=1;
            el2=arr[i];
        }
        else if(arr[i]==el1) cnt1++;
        else if(arr[i]==el2) cnt2++;
        else{
            cnt1--;
            cnt2--;
        }
    }

    vector<int> ans;

    cnt1=0,cnt2=0;
    for(int i=0;i<n;i++){
        if(arr[i]==el1){
            cnt1++;
        }

        if(arr[i]==el2){
            cnt2++;
        }
    }

    int mini=(int)(n/3)+1;
    if(cnt1 >= mini) ans.push_back(el1);
    if(cnt2 >= mini) ans.push_back(el2);

    sort(ans.begin(),ans.end());
    return ans;

}