class Solution {
    public List<Integer> majorityElement(int[] nums) {
        List<Integer> ar = new ArrayList<>();
        int cnt1 = 0;
        int cnt2 = 0;
        int ele1 = Integer.MIN_VALUE;
        int ele2 = Integer.MIN_VALUE;
        for (int i = 0; i < nums.length; i++) {
            if (cnt1 == 0 && nums[i] != ele2) {
                ele1 = nums[i];
                cnt1++;
            } else if (cnt2 == 0 && nums[i] != ele1) {
                ele2 = nums[i];
                cnt2++;
            } else if (ele1 == nums[i]) {
                cnt1++;
            } else if (ele2 == nums[i]) {
                cnt2++;
            } else {
                cnt1--;
                cnt2--;
            }
        }
        cnt1=0;
        cnt2=0;
        for(int x:nums){
            if(ele1==x)
                cnt1++;
            else if(ele2==x){
                     cnt2++;
            }
        }
        if(cnt1>(nums.length/3))
            ar.add(ele1);
        if(cnt2>(nums.length/3))
            ar.add(ele2);
        return ar;
    }
}