229. Majority Element II

Description

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

 

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

 

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

Solution

majority-element-ii.py

class Solution:
    def majorityElement(self, nums: List[int]) -> List[int]:
        if not nums: return []

        maj1, maj2, count1, count2 = 0, -1, 0, 0

        for num in nums:
            if num == maj1:
                count1 += 1

            elif num == maj2:
                count2 += 1

            elif count1 == 0:
                maj1, count1 = num, 1

            elif count2 == 0:
                maj2, count2 = num, 1

            else:
                count1 -= 1
                count2 -= 1

        return [n for n in (maj1, maj2) if nums.count(n) > len(nums) // 3]