Problem statement

https://binarysearch.com/problems/Submajority-Vote/

Solution

Almost equal to Leetcode 0229. Majority Element II. Sort in the end.

Complexity

It is O(n) for time and O(1) for space.

Code

class Solution:
    def solve(self, nums):
        count = Counter()
        for num in nums:
            count[num] += 1
            if len(count) == 3:
                new_count = Counter()
                for elem, freq in count.items(): 
                    if freq != 1: new_count[elem] = freq - 1
                count = new_count
                    
        cands = Counter(num for num in nums if num in count)      
        return sorted([num for num in cands if cands[num] > len(nums)/3])