Skip to content

169. Majority Element

Array Hash Table Divide and Conquer Sorting Counting

Problem - Majority Element

Easy

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.

 

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

 

Follow-up: Could you solve the problem in linear time and in O(1) space?

Solutions

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        # count = Counter(nums)
        # max_num = max(count.values())
        # return next(key for key, val in count.items() if val == max_num)

        # nums = sorted(nums)
        # return nums[len(nums)//2]

        count = maj = 0
        for num in nums:
            if count == 0:
                maj, count = num, 1
            else:
                count += 1 if num == maj else -1

        return maj

Submission Stats:

  • Runtime: 165 ms (5.58%)
  • Memory: 18 MB (100.00%)