'''
There can be 2 elements in any with more than n//3 occurance because n//3 + n//3+ n//3 > n is impossible.
Phase 1-> Find potential candidate-> if current element ==candidate 1, increase it's count and similarly check for other element and if no elements in any of them then, place them. using the phase 1 you got the potential elment

so using the above logic even if arr is like [1,2,3,4,5] still you will get 2 elements so to check them are their frequency is actually more than n//3,you check it manually and return them as the output.

***Always increment first then populate the None condition because if you will populate first the None,then suppose you got array like [1,1,2] then at the i=2, cand1=1 and cand2=1 because count1 is non-zero and count2 is zero***
'''
class Solution:
    def majorityElement(self, nums: List[int]) -> List[int]:
        if not nums:
            return []

        # Phase 1: Find candidates
        cand1, cand2 = None, None
        count1, count2 = 0, 0

        for num in nums:
            if num == cand1:
                count1 += 1
            elif num == cand2:
                count2 += 1
            elif count1 == 0:
                cand1, count1 = num, 1
            elif count2 == 0:
                cand2, count2 = num, 1
            else:
                count1 -= 1
                count2 -= 1

        # Phase 2: Verify counts
        result = []
        n = len(nums)

        if nums.count(cand1) > n // 3:
            result.append(cand1)
        if cand2 != cand1 and nums.count(cand2) > n // 3:
            result.append(cand2)

        return result