LeetCode DSA Series #7: 169. Majority Element

Source: Dev.to

Problem

This is my run at day 7 of the challenge (I missed yesterday’s submission). The problem today is 169. Majority Element.

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.

Solution

from collections import Counter
from typing import List

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        counts = Counter(nums)
        majority = len(nums) / 2

        for k, v in counts.items():
            if v > majority:
                return k

Complexity

• Time: O(N) – we traverse the list once to build the counter and once more to find the majority.
• Space: O(N) – the counter may store up to N distinct elements.