# 229. Majority Element II

"""
given an integer array of size 'n', find all elements that appear more than n
/ 3 times (floored)
"""


class Solution(object):
    def majorityElement(self, nums):
        if not nums:
            return []
        cnt1, cnt2, cdd1, cdd2 = 0, 0, 0, 1
        for n in nums:
            if n == cdd1:
                cnt1 += 1
            elif n == cdd2:
                cnt2 += 1
            elif cnt1 == 0:
                cdd1, cnt1 = n, 1
            elif cnt2 == 0:
                cdd2, cnt2 = n, 1
            else:
                cnt1, cnt2 = cnt1 - 1, cnt2 - 1
        return [n for n in (cdd1, cdd2) if nums.count(n) > len(nums) // 3]


if __name__ == "__main__":
    obj = Solution()
    print(obj.majorityElement([3, 2, 3]))  # expect: 3
    print(obj.majorityElement([1]))  # expect: 1
    print(obj.majorityElement([1, 2]))  # expect: 1 2