[LeetCode Solution] 169. Majority Element

Problem Description

LeetCode 169. Majority Element

Find the element that appears more than n/2 times in a list.

Solution

Approach: Two Pointer

1) Traverse the entire list and create a dictionary. 2) Return the value in the dictionary that appears more than n/2 times.

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        dic = {}
        for i in nums:
            if i not in dic:
                dic[i] = 1
            dic[i] += 1
        
        leng = len(nums)
        for i, v in dic.items():
            if v > leng//2 + 1:
                return i

The time and space complexity of the above solution are as follows:

• Time Complexity: O(N)
  • We iterate through the list nums, resulting in O(N) time complexity.
• Space Complexity: O(N)
  • We use a dictionary that grows with the size of nums, resulting in O(N) additional space usage.