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.