Find the Majority Element in an Array

Problem

A majority element in an array is an element that appears more than n/2 times, where n is the size of the array.
Given an array arr, find the majority element, or return -1 if it doesn’t exist.

Examples

Input

arr = [1, 1, 2, 1, 3, 5, 1]

Output

1

Explanation: 1 appears 4 times, which is more than 7/2 → majority element.

Input

arr = [7]

Output

7

Explanation: Single element → automatically majority element.

Input

arr = [2, 13]

Output

-1

Explanation: No element occurs more than 2/2 → no majority element.

Approach

Boyer-Moore Voting Algorithm (efficient):

Initialize a candidate and count = 0.
Traverse the array:
If count == 0, set candidate = current element.
If current element == candidate, increment count.
Else, decrement count.
After one pass, candidate is a potential majority element.
Verify by counting its occurrences.
If it occurs more than n/2 times → return it; else return -1.

Python Code
class Solution:
def majorityElement(self, arr):
candidate = None
count = 0

    # Step 1: Find candidate
    for num in arr:
        if count == 0:
            candidate = num
        if num == candidate:
            count += 1
        else:
            count -= 1

    # Step 2: Verify candidate
    if arr.count(candidate) > len(arr) // 2:
        return candidate
    else:
        return -1

Output
1