Problem Statement

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times.

Follow-up: Could you solve the problem in linear time and in O(1) space?

Example 1:

Input: nums = [3,2,3]
Output: [3]

Example 2:

Input: nums = [1]
Output: [1]

Example 3:

Input: nums = [1,2]
Output: [1,2]

Constraints:

• 1 <= nums.length <= 5 * 104
• 109 <= nums[i] <= 109

Problem Link

Majority Element II - LeetCode

Reference Video

https://www.youtube.com/watch?v=vwZj1K0e9U8&t=1s&ab_channel=takeUforward

Code

class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {

        int n = nums.size();

        int count1 = 0, count2 = 0, ele1,ele2;

        for(int i=0;i<n;i++) {
            if(count1==0&&nums[i]!=ele2) {
                ele1 = nums[i];
                count1 = 1;
            } else if(count2==0&&nums[i]!=ele1) {
                ele2 = nums[i];
                count2 = 1;
            } else if(ele1==nums[i]) {
                count1++;
            } else if(ele2==nums[i]) {
                count2++;
            } else {
                count1--;
                count2--;
            }
        }

         count1 = 0, count2 = 0;

        for(int num:nums) {
            if(ele1==num) {
                count1++;
            } else if(ele2==num) {
                count2++;
            } 
        }

        vector<int> res;

        if(count1>n/3) {
            res.push_back(ele1);
        }

        if(count2>n/3) {
            res.push_back(ele2);
        }
        
        return res;
    }
};