Friedrich Ewald My Personal Website

Leetcode: Majority number

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. Unfortunately, it is not clear from the description whether there are only two different numbers or multiple ones. Some of the solutions seem to suggest that there are only two different ones. The solution that I will show has a time complexity of O(n) and a space complexity of O(n) in the worst case, that is, if all the numbers appear exactly once.

from typing import List, Optional

class Solution:
  def majorityElement(self, nums: List[int]) -> int:
    m = {}
    max_n = nums[0]
    count_n = 1
    for n in nums:
      if n not in m:
        m[n] = 0
      m[n] += 1
      if m[n] > count_n:
        max_n = n
        count_n = m[n]
    return max_n

if __name__ == '__main__':
  s = Solution().majorityElement
  print(s([3,2,3]), 3)
  print(s([2,2,1,1,1,2,2]), 2)
A temporary map is used to count elements. If the elemented appeared more than the max element, it will be the new most frequent element. A possible optimization is to stop once the count reaches > n/2.

About the author

is an experienced Software Engineer with a Master's degree in Computer Science. He started this website in late 2015, mostly as a digital business card. He is interested in Go, Python, Ruby, SQL- and NoSQL-databases, machine learning and AI and is experienced in building scalable, distributed systems and micro-services at multiple larger and smaller companies.