Question : You are given an array , You need to find out if there is an element which has occurence more than n/2 times (where n is size of the array) and return it .

Input : {3, 3, 4, 2, 4, 4, 2, 4, 4}
Output : 4
Explanation: The frequency of 4 is 5 which is greater
than the half of the size of the array size. 

Brute Solution :

To get the answer , you can store the frequnecies of all array elements in an additional array and then iterate the frequency array and check if there is element with n/2 frequency . But if you take an array here , first you need to find the maximum array element and then allot the size according to that , so better to take a map and check the frequency every time .

Pseduo code :
map<int,int>m ;
for(i=0 to n-1)
{ m[ar[i]]++;}
if(m[ar[i]] > n/2){
return ar[i];
}
}
Time complexity : O(n)
Space complexity : O(n)

Optimal Solution :

Moore Voting Algorithm:

To get the optimal solution we will be using moore voting algorithm here.So basically it gonna remove the extra space we are using .
This algorithm intially takes ele=0 and count=0 and you lineraly iterate from first element to last element . When you hit a element you first check if count is zero , if it is so , then you store the current element in ele .
In next step , check if your ele is same as current array element if it is so then increase your count variable else decrease your count variable .
Pseudo code for these two steps :
if(count==0)
{ ele=ar[i] ; }
if( ele==ar[i] ) {
count++;
}
else {
count–;
}
Idea , behind this algorithm is : whenever we find a element we claim that this is our required element and next time we hit this element we increase the count and whenever we found something else we decrease the count.Ultimately whichever is stored as ele , that is our answer .

Code :
C++
Function to find the element with n/2 occurences :

int majorityElement(vector<int>& nums) {

    int cnt=0;
    int el=0;

    for(int i=0;i<nums.size();i++)
    {
        if(cnt==0)
        {
            el=nums[i];
        }

        if(el==nums[i])
        {
            cnt++;
        }
        else
        {
            cnt--;
        }
    }

    return el;


}

Time Complexity : O(n)
Space Complexity : O(n)