Majority Element II

TARGET DECK: Leetcode FILE TAGS:

Intuition

• Similar to Majority Element, we understand that there is only one element “possible” that has a count > floor of $\frac{N}{2}$. You can visualize this by having a water jug half full, in which only one element can be more than half full.
• Then, it follows that there can be only two elements > $\frac{N}{3}$ full.
• In this question unlike Majority Element, there is no guarantee that any element appear more than $\frac{N}{3}$ times.
• Yet, it still holds that if there are such elements, there can be at most two of them.
• To sum up those candidates, use the Boyer Moore Algorithm, which finds the two elements that can be N / 3 times full.
• If they do indeed occur more than N / 3 times, then that candidate must be the majority element.
  • This is because once an element surpasses $\frac{N}{3}$, that element cannot be overridden again.

Cards

START Basic Front: Majority Element - LeetCode Back: Once an element surpasses $\frac{N}{3}$, there cannot be another element that surpasses that element.

END

Complexity

Runtime

$O(N)$ to iterate in 2 passes

Space

$O(1)$ to store the candidates

Code

Boyer Moore

class Solution:
    def majorityElement(self, nums: List[int]) -> List[int]:
        candidate1, count1 = None, 0
        candidate2, count2 = None, 0
 
        # 1st pass: Find the elements that "have the possibility of occuring more than n / 3 times"
        for num in nums:
            if candidate1 == num:
                count1 += 1
            elif candidate2 == num:
                count2 += 1
            elif count1 == 0:
                candidate1 = num
                count1 += 1
            elif count2 == 0:
                candidate2 = num
                count2 += 1
            else:
                count1 -= 1
                count2 -= 1
        
        # 2nd pass: See which of those candidates is indeed greater than the floor of n / 3
        res = []
        n = len(nums)
        for candidate in [candidate1, candidate2]:
            if nums.count(candidate) > n // 3:
                res.append(candidate)
        return res

Hashmap O(N) Space

class Solution:
    def majorityElement(self, nums: List[int]) -> List[int]:
        n = len(nums)
        c = Counter(nums)
        res = []
        for k in c:
            if c[k] > n // 3:
                res.append(k)
        return res

Notes

---

References

Majority Element II - LeetCode