169. Majority Element

Easy

Problem:

Print the element that constitutes a majority (more than half).

Example 1:

Input: nums = [3,2,3]
Output: 3

Example 2:

Input: nums = [2,2,1,1,1,2,2]
Output: 2

https://leetcode.com/problems/majority-element

Solution:

Divide and Conquer

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
    
        if len(nums) == 1:
            return nums[0]
        
        half = len(nums) // 2
        a = self.majorityElement(nums[:half])
        b = self.majorityElement(nums[half:])
        # TRUE -> 1
        return [a, b][nums.count(b) > half]

Dynamic programming

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        counts = collections.defaultdict(int)
        for num in nums:
            if counts[num] == 0:
                # Memoization
                counts[num] = nums.count(num)
                
            if counts[num] > len(nums) // 2:
                return num

Pythonic way

By sorting and choosing the middle element, it will definitely be the element that constitutes more than a majority. It's a very intuitive and simple algorithm.

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        return sorted(nums)[len(nums) // 2]