Python Program to Find Majority Element in Array

You can find the majority element in an array using Python by counting each element's frequency and returning the element that appears more than half the array length, for example: max(set(arr), key=arr.count).

Examples

Input[3, 3, 4, 2, 4, 4, 2, 4, 4]

Output4

Input[1, 2, 3, 2, 2]

Output2

Input[1, 1, 2, 3, 1]

Output1

How to Think About It

To find the majority element, think about which number appears more than half the time in the list. You can count how many times each number shows up and pick the one with the highest count that is more than half the list size.

Algorithm

1

Get the input array.

2

Count how many times each element appears.

3

Find the element with the highest count.

4

Check if this count is more than half the length of the array.

5

Return this element as the majority element.

Code

python

def find_majority_element(arr):
    n = len(arr)
    for num in set(arr):
        if arr.count(num) > n / 2:
            return num
    return None

# Example usage
arr = [3, 3, 4, 2, 4, 4, 2, 4, 4]
print(find_majority_element(arr))

Output

4

Dry Run

Let's trace the example array [3, 3, 4, 2, 4, 4, 2, 4, 4] through the code.

1

Calculate length

Length n = 9

2

Check unique elements

Unique elements are {2, 3, 4}

3

Count occurrences

Count of 2 = 2, count of 3 = 2, count of 4 = 5

4

Compare counts to half length

Half length = 4.5, 4 appears 5 times which is > 4.5

5

Return majority element

Return 4

Element	Count	Is Majority?
3	2	No
4	5	Yes
2	2	No

Why This Works

Step 1: Counting elements

The code counts how many times each unique element appears using arr.count(num).

Step 2: Checking majority condition

It compares the count to half the array length using n / 2 to find if an element is majority.

Step 3: Returning the majority element

Once an element with count greater than half is found, it returns that element immediately.

Alternative Approaches

Boyer-Moore Voting Algorithm

python

def majority_element_boyer_moore(nums):
    count = 0
    candidate = None
    for num in nums:
        if count == 0:
            candidate = num
        count += (1 if num == candidate else -1)
    return candidate

arr = [3, 3, 4, 2, 4, 4, 2, 4, 4]
print(majority_element_boyer_moore(arr))

This method uses constant space and linear time, making it efficient for large arrays.

Using Dictionary to Count Frequencies

python

def majority_element_dict(arr):
    counts = {}
    n = len(arr)
    for num in arr:
        counts[num] = counts.get(num, 0) + 1
        if counts[num] > n / 2:
            return num
    return None

arr = [3, 3, 4, 2, 4, 4, 2, 4, 4]
print(majority_element_dict(arr))

This approach uses extra space for the dictionary but finds the majority element in one pass.

Complexity: O(n^2) time, O(n) space

Time Complexity

The main code uses arr.count() inside a loop over unique elements, which leads to O(n^2) time in worst case.

Space Complexity

It uses O(n) space for the set of unique elements; no extra data structures are heavily used.

Which Approach is Fastest?

The Boyer-Moore Voting Algorithm runs in O(n) time and O(1) space, making it the fastest and most memory-efficient.

Approach	Time	Space	Best For
Counting with arr.count()	O(n^2)	O(n)	Small arrays or simple code
Boyer-Moore Voting Algorithm	O(n)	O(1)	Large arrays, best performance
Dictionary Counting	O(n)	O(n)	When clarity and single pass needed