Problem Statement

Description

Given an array nums of size n, return the majority element.

The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.

Examples

Example 1:

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

Example 2:

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

Constraints

  • n == nums.length
  • 1 <= n <= 5 * 104
  • -109 <= nums[i] <= 109

Key Insights

There are many different ways to solve this problem. We’ll take a look at two of the simplest approaches. We can use a hash map to keep track of the frequency of each number or we could sort the list and return the middle value.

Note: Since we know that the majority element appears more than n/2 times in the list, we know that it will make up more than 50% of the elements in the array. Consequently, the middle element n//2 will always be the majority element.

Python Solution

Hash Map Solution

from collections import Counter

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        """
            T: O(N)
            S: O(N)
        """
        n = len(nums)
        mp = Counter(nums)

        for number, frequency in mp.items():
            if frequency > (n // 2):
                return number

Sorting Solution

from collections import Counter

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        """
            T: O(N log N)
            S: O(1) ~ best case; O(N) ~ worst case
        """
        n = len(nums)
        nums = sorted(nums)

        return nums[n // 2]