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

Let us iterate through our data and at each moment of time keep at most 2 candidates with the highest score, let us consider example 1 2 3 3 3 2 2 2 4 2.

  1. On first step we add 1 to our candidates, frequency 1, so we have 1: 1
  2. Now we add 2 to our candidates, frequency 1, so we have 1:1, 2:1.
  3. Now we add 3 to our candidates and we have 1:1, 2:1, 3:1. Now we subtract 1 from all frequencies, because it will not change anything.
  4. Now we add 3, so we have 3:1.
  5. Now we add 3, so we have 3:2.
  6. Now we add 2, so we have 3:2, 2:1.
  7. Now we add 2, so we have 3:2, 2:2.
  8. Now we add 2, so we have 3:2, 2:3.
  9. Now we add 4, so we have 3:2, 2:3, 4:1, subtract 1 from all, and we have 3:1, 2:2.
  10. Finally we add 2, so we have 3:1, 2:3.

First stage of our algorithm is finished, we have no more than two candidates. Now we need to make sure, that these candidates indeed has frequence more than [n/3]. So we iterate through our data once again and count them. In our case 2 is true candidate and 3 need to be removed, its frequency is not big enough.

Complexity: Time complexity is O(n), because we traverse our nums twice: on first run we process each number at most twice: when we add it to counter and when remove. Second run, where we evaluate frequencies of candidates is also linear. Space complexity is O(1), because our counter always have no more than 3 elements.

class Solution:
    def majorityElement(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 [num for num in cands if cands[num] > len(nums)/3]

If you like the solution, you can upvote it on leetcode discussion section: Problem 0229