Majority Element

#include<bits/stdc++.h>

vector<int> majorityElement(vector<int> v) {

    map<int,int>mpp;

    vector<int>res;

    for(int i=0;i<v.size();i++)

    {

        mpp[v[i]]++;

    }   

    for(auto it:mpp)

    {

        if(it.second>(v.size()/3))

        {

            res.push_back(it.first);

        }

    }

    return res;

}

vector<int> majorityElement(vector<int> v) {

    int n=v.size();

    vector<int>res;

    for(int i=0;i<n;i++)

    {

        int cnt=0;

        for(int j=i;j<n;j++)

        {

            if(v[j]==v[i])

            {

                cnt++;

            }

        }

        if (cnt > n / 3 && find(res.begin(), res.end(), v[i]) == res.end()) {

            res.push_back(v[i]);

        }

    }

    return res;

}

The code you provided now correctly implements the Boyer-Moore Voting Algorithm for finding elements that appear more than `n/3` times. The main steps of the algorithm are as follows:

### Explanation of the Algorithm:

1. **Candidate Selection (Phase 1):**   - The algorithm aims to find at most two candidates (`el1` and `el2`) that could potentially appear more than `n/3` times in the array.   - We keep track of two candidate elements and their respective counts (`count1` and `count2`).   - As we iterate through the array:     - If `count1` is zero and the current element is different from `el2`, we update `el1` to the current element and set `count1` to 1.     - If `count2` is zero and the current element is different from `el1`, we update `el2` to the current element and set `count2` to 1.     - If the current element matches `el1`, we increment `count1`.     - If the current element matches `el2`, we increment `count2`.     - If the current element does not match either `el1` or `el2`, we decrement both `count1` and `count2`.

2. **Candidate Verification (Phase 2):**   - After identifying the two potential candidates, we need to verify if they actually appear more than `n/3` times in the array.   - We iterate through the array again to count the occurrences of `el1` and `el2`.   - If the occurrences of `el1` are greater than `n/3`, we add it to the result list.   - If the occurrences of `el2` are greater than `n/3`, we add it to the result list.

### Code Correction Summary: The corrected code now appropriately: - Checks the two potential candidates (`el1` and `el2`) against all elements in the array to verify if they occur more than `n/3` times. - Ensures that both candidates are checked separately and added to the result list if they meet the criteria.

### Complexity Analysis: - **Time Complexity:** O(n), where n is the length of the array. The algorithm makes two passes through the array (one for finding candidates and one for verifying them). - **Space Complexity:** O(1), as the algorithm uses a fixed amount of extra space.

### Final Note: The provided implementation efficiently finds all elements that appear more than `n/3` times in the array using the Boyer-Moore Voting Algorithm.

def majorityElement(v: [int]) -> [int]:

    sett=[]

    n=len(v)

    v.sort()

    r=v[0]

    cnt=0

    time=n//3

    if n==0:

        return sett

    for i in range(n):

        if v[i]==r:

            cnt+=1

        if cnt>time:

            sett.append(v[i])

            cnt=0

        if v[i]!=r:

            cnt=1

            r=v[i]   

    if len(sett)>1:

        return sett[0],sett[1]

    else:

        return sett

💡 The problem is to find elements that appear more than ⌊n/3⌋ times in an array. If you think about it, there can be at most 2 elements in an array that meet this condition. This is because if there were 3 or more such elements, their total count would exceed n. Thus, we can use a modified version of the Boyer-Moore Voting Algorithm to identify these two potential candidates.

🚀 Step-by-Step Approach:

1. Initialization: Start with two candidate variables (candidate1 and candidate2) and their counts (count1 and count2), both initialized to 0.
2. First Pass (Find Candidates): Traverse through the array to find the two most likely candidates that could appear more than n/3 times.
   • If the current number matches one of the candidates, increment its count.
   • If the current number does not match any candidate and one of the counts is 0, assign the current number as the new candidate and set its count to 1.
   • If the current number does not match any candidate and both counts are not 0, decrement both counts.
3. Second Pass (Verify Candidates): Traverse the array again to count the occurrences of the two candidates.
4. Result Preparation: Check if the count of each candidate is greater than n/3. If so, add it to the result list.

• Time Complexity:
  • O(n): The solution involves two passes through the array, each taking linear time.
• Space Complexity:
  • O(1): Only a few extra variables are used to keep track of the two candidates and their counts.

vector<int> majorityElement(vector<int>& nums) {

int count1 = 0, count2 = 0;

        int element1 = INT_MIN, element2 = INT_MIN;

        // Find the potential majority elements

        for (int num : nums) {

            if (count1 == 0 && num != element2) {

                count1 = 1;

                element1 = num;

            } else if (count2 == 0 && num != element1) {

                count2 = 1;

                element2 = num;

            } else if (num == element1) {

                count1++;

            } else if (num == element2) {

                count2++;

            } else {

                count1--;

                count2--;

            }

        }

        // Verify the majority elements

        count1 = 0, count2 = 0;

        for (int num : nums) {

            if (num == element1) {

                count1++;

            } else if (num == element2) {

                count2++;

            }

        }

        vector<int> ans;

        if (count1 > nums.size() / 3) {

            ans.push_back(element1);

        }

        if (count2 > nums.size() / 3) {

            ans.push_back(element2);

        }

        return ans;

    }

#include<bits/stdc++.h>

vector<int> majorityElement(vector<int> v) {

     map<int, int> res;

    vector<int> ls;

    int n=v.size();

    int mini=(int)(n/3)+1;

    for (int i = 0; i < v.size(); i++) {

        res[v[i]] = res[v[i]] + 1;

        if (res[v[i]] == mini) {

            ls.push_back(v[i]);

        }

        if (ls.size() == 2) {

            break;

        }

    }

    sort(ls.begin(),ls.end());

    return ls;

}

There should be only two element which are greater than n/3.so,count for two different elements

#include <bits/stdc++.h>

vector<int> majorityElement(vector<int> v) {

    int e1=INT_MIN,e2=INT_MIN;

    int count_1=0,count_2=0;

    for(int i=0;i<v.size();i++)

    {

        if(count_1==0 &&  v[i]!=e2)

        {

            count_1++;

            e1=v[i];

        }

        else if (count_2==0 && v[i]!=e1)

        {

            count_2++;

            e2=v[i];

        }

        else if (e1==v[i])  {

            count_1++;

        }

        else if (e2==v[i])

        {

            count_2++;

        }

        else{

            count_1--;

            count_2--;

        }

    }

    count_2=0,count_1=0;

    for(int i=0;i<v.size();i++)

    {

        if(v[i]==e1) count_1++;

         if(v[i]==e2) count_2++;

    }

    vector<int> ans;

    int n=v.size();

    int check=floor(n/3)+1;

    if(count_1>=check )

    {

        ans.push_back(e1);

    }

    if(count_2>=check )

    {

        ans.push_back(e2);

    }

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

    return ans;

}

def majorityElement(v: [int]) -> [int]:

    n = len(v)

    freq = {}

    final = []

    for i in v:

        if i in freq:

            freq[i] += 1

        else:

            freq[i] = 1

    for key, value in freq.items():

        if value > n // 3:

            final.append(key)

    return sorted(final)