coding_practice/majority_element_II.cpp at main · ashish095-EE/coding_practice · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56


class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {
        int cnt1=0,cnt2=0;
        int element1=INT_MIN,element2=INT_MIN;

        for(int i=0;i<nums.size();i++){
            if(cnt1==0&&element2!=nums[i]){
                cnt1=1;
                element1=nums[i];

            }
            else if(cnt2==0&&element1!=nums[i]){
                cnt2=1;
                element2=nums[i];

            }
            else if(nums[i]==element1)cnt1++;
            else if(nums[i]==element2)cnt2++;

            else{
                cnt1--;
                cnt2--;
            }


        }

        vector<int> result;
        int threshold = nums.size() / 3; // Threshold for majority element

        // Second pass to count occurrences of the potential majority elements.
        cnt1 = 0, cnt2 = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (element1 == nums[i]) {
                cnt1++;
            } else if (element2 == nums[i]) {
                cnt2++;
            }
        }

        // Check if the counts of potential majority elements are greater than n/3 and add them to the result.
        if (cnt1 > threshold) {
            result.push_back(element1);
        }
        if (cnt2 > threshold) {
            result.push_back(element2);
        }

        return result;


    }
};