DEV Community

Shahrouz Nikseresht
Shahrouz Nikseresht

Posted on

Day 45: Python Majority Element Finder, Boyer-Moore Voting Algorithm for Efficient Detection in Arrays

#challenge #python #intermediate #programming

Welcome to Day 45 of the #80DaysOfChallenges journey! This intermediate challenge implements the Boyer-Moore Majority Vote Algorithm to find the element appearing more than n/2 times in a list, achieving O(n) time and O(1) space by tracking a candidate and count without sorting or hashing. It's a clever algorithmic trick for voting-style problems, teaching phase-based candidate selection and counter adjustments, common in streaming data or interview questions. If you're advancing from basic arrays to optimized algorithms or need constant space solutions, this "Python majority element" script demonstrates a function that's ingenious, assumes a majority exists, and easy to verify with extensions for no-majority cases.

💡 Key Takeaways from Day 45: Majority Element Function

This task features a single function that scans the list once, updating a candidate based on count increments/decrements, relying on the majority guarantee for correctness. It's a voting simulation: majority "votes" overpower minorities. We'll detail: function with candidate and count tracking, loop for vote logic, and main with input parsing.

1. Function Design: Candidate and Count Initialization

The majority_element function takes a list and returns the majority:

def majority_element(nums):
    """
    Track a candidate and adjust count.
    Majority exists, so candidate at the end is the answer.
    """
    candidate = None
    count = 0
Enter fullscreen mode Exit fullscreen mode

None starts candidate, 0 for count. This O(1) space is key, no extra structures needed.

2. Loop Processing: Vote Increment and Decrement

Core loop scans each num:

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

return candidate
Enter fullscreen mode Exit fullscreen mode

If count 0, set new candidate (start phase). +1 if matches, -1 else. Majority survives as candidate. For [2,2,1,1,1,2,2]: 1 becomes candidate but 2 wins. O(n) time, single pass.

3. Main Interactive: Input and Call

Script reads list and calls:

arr = list(map(int, input("Enter numbers separated by space: ").split()))
result = majority_element(arr)
print(f"Majority element: {result}")
Enter fullscreen mode Exit fullscreen mode

Splits input to ints, calls function, prints. Assumes valid, majority present.

🎯 Summary and Reflections

This Boyer-Moore finder shows elegant efficiency for majorities. It reinforced:

  • Phase concept: Resets on count 0, majority prevails.
  • Space optimization: O(1) by avoiding counts.
  • Assumption use: Guarantee skips verification pass.

Two phases possible if no majority, add count verify. For fun, handle ties.

Advanced Alternatives: Hash count: Counter(nums).most_common(1), O(n) space. Sort: nums[n//2] after sort. Your majority method? Share!

🚀 Next Steps and Resources

Day 45 optimized array algos, prepping for streams. In #80DaysOfChallenges? Handled no majority? Post!

Top comments (0)