Majority Element

Hi everyone!
Today I solved a very interesting problem where we need to find the majority element in an array. The cool part is that it can be solved in O(n) time and O(1) space.

Problem
Given an array, find the element that appears more than n/2 times.
If no such element exists, return -1.

Example:
Input: [1, 1, 2, 1, 3, 5, 1]

Output: 1

My Approach
At first, I thought of using a hashmap to count frequencies.
But that takes extra space.
Then I learned about:

Boyer-Moore Voting Algorithm

Logic
Maintain a candidate and a count
Traverse the array:
If count becomes 0 - choose new candidate
If element equals candidate - increase count
Else - decrease count
Finally, verify if candidate is actually majority

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

    for num in arr:
        if count == 0:
            candidate = num

        if num == candidate:
            count += 1
        else:
            count -= 1

    # Verify candidate
    if arr.count(candidate) > len(arr) // 2:
        return candidate

    return -1

Time & Space Complexity
Time: O(n)
Space: O(1)

Key Insight
Majority element cannot be fully cancelled out, so it will remain as the final candidate.

What I Learned
Advanced algorithms can reduce space complexity
Voting/cancellation idea is very powerful
Always verify the result in such problems

Thanks for reading!
Feel free to share other approaches like hashmap or sorting.