Leetcode 229. Majority Element II

Problem

Leetcode 122 - Majority Element II

Example:

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

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

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

Approach

We can use a HashMap to count the frequency of each element, then we can iterate through this HashMap to return elements with frequency that has more than $\frac{n}{3}$. However the problem with this solution is that the space complexity would be $O(n)$ since we’re tracking all the element’s frequency.

We can use these facts about the problem to solve this quesiton:

• What we need to return are elements with frequency that is more than $\frac{n}{3}$: Meaning that there are at most 2 elements

Using this fact, we can approach this problem by saving only 2 elements at most in our HashMap.

We can iterate through our array like we would before and adding the element and frequency of first two. Then once we encounter a 3rd unique element, we decrement all the frequency by 1, and when they’re 0, we pop them out of the HashMap and continue. Whatever elements are left in the end in HashMap, we check if there are more than $\frac{n}{3}$. We will see the example below

Visualization of the Approach:

Example 1.

nums = [1, 2, 3, 1, 2]
map = {}

map = { 1: 1 }

map = { 1: 1, 2: 1 }

map = { 1: 1, 2: 1, 3: 1 }
Since there are more than 2 elements in map, we decrement each value by 1, and if they're 0 we pop them out

map = {}

map = { 1: 1 }

map = { 1: 1, 2: 1 }

Now that we're done, we check if 1 and 2 have more than n/3 counts
1 has 2, 2 has 2, and n/3 = 1. Since 1 and 2 have more than 1, we return 1, 2

Example 2.

nums = [1, 2, 3, 4, 5, 6]
map = {}

map = { 1: 1 }

map = { 1: 1, 2: 1 }

map = { 1: 1, 2: 1, 3: 1 }
Since there are more than 2 elements in map, we decrement each value by 1, and if they're 0 we pop them out

map = { 4: 1 }

map = { 4: 1, 5: 1 }

map = { 4: 1, 5: 1, 6: 1 }
Since there are more than 2 elements in map, we decrement each value by 1, and if t hey're 0 we pop them out

map = {}

Thus, we reutrn empty array

Here is the Python code for the solution:

class Solution:
    def majorityElement(self, nums: List[int]) -> List[int]:
        count = defaultdict(int)

        # iterating through array
        for num in nums:
            count[num] += 1

            # if count length is 2 or less we continue
            if len(count) <= 2:
                continue
            
            # if count length is more than 2, we decrement each count
            new_count = defaultdict(int)
            for num, c in count.items():
                if c > 1:
                    new_count[num] = c - 1
            
            count = new_count
        
        res = []
        for num in count:
            if nums.count(num) > len(nums) // 3:
                res.append(num)
        
        return res

Time Complexity and Space Complexity

Time Complexity: $O(n)$

Space Complexity: $O(1)$, since at most we’re storing 2 elements in HashMap