Python O(n) time O(1) space, two simple solutions

  • 0

    First solution is one pass using a dictionary.

     def majorityElement(self, nums):
          dic = {}
          for num in nums:
               dic[num] = dic.get(num,0) + 1
               if dic[num] > len(nums)//2:
                    return num

    Second solution uses constant space and increments/decrements until the last element left is the majority element (thank you jojocat1010 for inspiration).

     def majorityElement(self, nums):
          major, count = None, 0
          for num in nums:
               major, count = [major, count+1 if major == num else count-1] if count else [num, 1] 
          return major

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.