Majority Element II

Repeating Number

Problem

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

Example:

Input: nums = [3,2,3]
Output: [3]

Input: nums = [1 2 3 1 1]
Output: [1] 

Thought Process

• Moore's Voting Algorithm: We have to use Moore's Voting Algorithm so we can find the potential candidates. Since Moore's Voting Algorithm finds the majority element in a sequence, this is perfect for finding the candidates that may appear more than ⌊ n/3 ⌋ times. In this case, there are two potential candidates.

• The reason why we can have 2 possible majority elements at max is because the problem asks us to find all elements that appear more than ⌊ n/3 ⌋ times. Suppose there are three elements that appeared more than ⌊ n/3 ⌋ times, then there needs to be at least $3 * ⌊ n/3 + 1 ⌋> n$ elements in the array, which is not possible ( $(n/3+1)+(n/3+1)+(n/3+1) > n)$ .

  • e.g. suppose $n = 9$, then the problem asks to find all elements that appeared more than 3 times, which means they have to appear at least 4 times. There can't be 3 items in the array of length 9 that all have appeared 4 times.

• Similar to Majority Element I, we will use Moore's Voting Algorithm to find two potential candidates to be later verified that they occur more than ⌊ n/3 ⌋ times.

Solution

class Solution:
    def majorityElement(self, nums: List[int]) -> List[int]:
   
        candA, countA = 0,0
        candB, countB = 0,0
        
        for n in nums:
            if candA == n:
                countA += 1
            elif candB == n:
                countB += 1
            elif countA == 0:
                candA = n
                countA = 1
            elif countB == 0:
                candB = n
                countB = 1
            else:
                countA-=1
                countB-=1
 

        countA = countB = 0
        for n in nums:
            if candA == n:
                countA += 1
            elif candB == n:
                countB += 1
        
        res = []
        if countA > len(nums) // 3:
            res.append(candA)
        if countB > len(nums) // 3:
            res.append(candB)
            
        return res

Key Facts

• We are using Moore's Voting Algorithm to find majority elements so that we can later verify that these elements occure more than⌊ n/3 ⌋ times. Moore's Voting Algorithm gives us potential candidates since it will find elements that occur the most. We have to then verify these elements.

• The reason why we can have two majority elements at max is because for finding $1/k$ majority, $k-1$elements can qualify.

Time Complexity

• Time: $O(n)$

• Space: $O(1)$