[LeetCode] 229. Majority Element II

Problem : https://leetcode.com/problems/majority-element-ii/

The total number of majority elements should less than 3.

class Solution:
    def majorityElement(self, nums: List[int]) -> List[int]:
        a = b = 0
        cnt1 = cnt2 = 0
        N = len(nums)
        
        for n in nums:
            if n == a:
                cnt1 += 1
            elif n == b:
                cnt2 += 1
            elif cnt1 == 0:
                a = n
                cnt1 += 1
            elif cnt2 == 0:
                b = n
                cnt2 += 1
            else:
                cnt1 -= 1
                cnt2 -= 1
        
        cnt1 = cnt2 = 0
        
        for n in nums:
            if n == a:
                cnt1 += 1
            if n == b:
                cnt2 += 1
        
        # verify the majority elements
        result = []
        if cnt1 > N // 3:
            result.append(a)
        if cnt2 > N // 3 and a != b:
            result.append(b)
        
        return result