Leetcode 169. Majority Element

Problem

Leetcode 169 - Majority Element

Example:

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

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

Approach

There are two methods on solving this problem:

1. Using Dict to count how many each elements are in the array
2. Since the question states that the majority element appears more than [n/2] times, we can just sort the array and return the middle of the array

Visualization of the Approach:

1. Using dict

nums = [2, 2, 1, 1, 1, 2, 2]
dict = { 1: 3, 2: 4} where x:count.
Since 2 has the most count, we return 2

2. Using sorting

nums = [2, 2, 1, 1, 1, 2, 2]

after sorting
nums = [1, 1, 1, 2, 2, 2, 2]

Thus return 2 since middle of array is 2.

Here is the Python code for the solution:

class Solution:
    # using the first method (dict)
    def majorityElement1(self, nums: List[int]) -> int:
        dict = {}
        for num in nums:
            if num not in dict:
                dict[num] = 1
            else:
                dict[num] += 1
        
        return max(zip(dict.values(), dict.keys()))[1]
    
    # using the second method (n/2)
    def majorityElement2(self, nums: List[int]) -> int:
        nums = sorted(nums)

        return nums[len(nums)//2]
            

Time Complexity and Space Complexity

Using Hash Map(dict)

Time Complexity: $O(n)$, since we’re iterating through the list

Space Complexity: $O(n)$, since we’re using dict

Using the fact that majority element count is $\frac{n}{2}$

Time Complexity: $O(n log n)$, depends on sorting algorithm

Space Complexity: $O(1)$