5 Best Ways to Find a Majority Element in Python

💡 Problem Formulation: A majority element in an array is an element that makes up more than half of its items. Given an array of size n, find the majority element. The array may be assumed to be non-empty and the majority element always exist in the array. For instance, in the array [3, 3, 4, 2, 4, 4, 2, 4, 4], the majority element is 4 since it appears five times and five is more than half of nine.

Method 1: HashMap Count

This method involves using a Python dictionary to count occurrences of each element. The key of the dictionary represents the array element, and the value represents the count of that element. Once an element’s count exceeds the halfway point of the array’s size, it is declared as the majority element.

Here’s an example:

from collections import Counter

def find_majority_element(nums):
    counts = Counter(nums)
    return max(counts.keys(), key=counts.get)

nums = [2, 2, 1, 1, 2, 2, 3]
print(find_majority_element(nums))

Output: 2

This code snippet uses the Counter class from the collections module to count the occurrences of elements. Then, it uses the max function with a key argument that retrieves the key with the maximum value in the dictionary, which corresponds to the majority element.

Method 2: Sorting

By sorting the array, the majority element can be found at the middle index position because it must appear at least once at the middle due to its requirement of occurring more than half the time in the array.

Here’s an example:

def find_majority_element(nums):
    nums.sort()
    return nums[len(nums) // 2]

nums = [3, 3, 4, 2, 4, 4, 2, 4, 4]
print(find_majority_element(nums))

Output: 4

This code sorts the list and returns the middle element. Due to the definition of a majority element, after sorting, the middle element of the array is guaranteed to be the majority element.

Method 3: Divide and Conquer

The divide and conquer approach splits the array into two halves and recursively finds the majority element in each half. The majority element of the entire array is the element that is the majority in one of the halves, or that appears most between the two majorities of the halves.

Here’s an example:

def majority_element_rec(nums, left, right):
    if left == right:
        return nums[left]
    mid = (left + right) // 2
    left_majority = majority_element_rec(nums, left, mid)
    right_majority = majority_element_rec(nums, mid + 1, right)

    left_count = sum(1 for i in range(left, right + 1) if nums[i] == left_majority)
    right_count = sum(1 for i in range(left, right + 1) if nums[i] == right_majority)

    return left_majority if left_count > right_count else right_majority

def find_majority_element(nums):
    return majority_element_rec(nums, 0, len(nums)-1)

nums = [1, 2, 2, 2, 3, 2, 2]
print(find_majority_element(nums))

Output: 2

This snippet defines a recursive function that uses a divide and conquer strategy. It splits the array into two halves, finds a majority candidate for each half, and then checks their occurrences in the entire array to find the majority element.

Method 4: Boyer-Moore Voting Algorithm

The Boyer-Moore Voting Algorithm is an optimal algorithm that finds the majority element in linear time and constant space. It operates by maintaining a count that increases when the current candidate is encountered again, and decreases when a different element is encountered. If the count reaches zero, a new candidate is picked.

Here’s an example:

def find_majority_element(nums):
    count = 0
    candidate = None

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

    return candidate

nums = [2, 2, 1, 1, 2, 2, 3]
print(find_majority_element(nums))

Output: 2

This code maintains a count of the candidate’s occurrences, updating the candidate whenever the count reaches zero. By the end of the loop, the current candidate must be the majority element due to the nature of the majority requirement.

Bonus One-Liner Method 5: Pythonic Approach with max() and list.count()

This Python one-liner uses the max() function combined with the list.count() method to identify the majority element by searching for the maximum occurrence.

Here’s an example:

find_majority_element = lambda nums: max(set(nums), key=nums.count)

nums = [1, 2, 2, 2, 3, 2, 2]
print(find_majority_element(nums))

Output: 2

This single line of code converts the list to a set to eliminate duplicates, then applies the max() function with a key that counts occurrences of each unique element in the list, finding the maximum, which corresponds to the majority element.

Summary/Discussion

• Method 1: HashMap Count. Strengths: Easy to implement and understand. Weaknesses: Requires O(n) extra space.
• Method 2: Sorting. Strengths: Simple and concise. Weaknesses: Modifies the original list and has O(n log n) time complexity.
• Method 3: Divide and Conquer. Strengths: Does not modify original list and is a classic approach. Weaknesses: More complex and requires additional space for recursive calls.
• Method 4: Boyer-Moore Voting Algorithm. Strengths: Optimal solution with O(n) time complexity and O(1) space. Weaknesses: Requires understanding of algorithm to implement correctly.
• Bonus One-Liner Method 5: Pythonic Approach. Strengths: Very concise and Pythonic. Weaknesses: Has poor performance O(n^2) due to list.count() operations within max().