🏆 Majority Element (Boyer-Moore Voting Algorithm)

The Majority Element problem is a classic question that tests your understanding of arrays and optimization techniques. It can be solved efficiently using a clever algorithm called the Boyer-Moore Voting Algorithm. 📌 Problem Statement Given an array arr[], find the element that appears more than n/2 times. If no such element exists, return -1. 🔍 Examples Example 1: Input: [1, 1, 2, 1, 3, 5, 1] Output: 1 Example 2: Input: [7] Output: 7 Example 3: Input: [2, 13] Output: -1 🧠 Intuition If an element appears more than n/2 times: 👉 It will always dominate the array 👉 It cannot be completely canceled out This idea leads to the Boyer-Moore algorithm. 🔄 Approach 1: Brute Force Count frequency of each element Check if any element appears more than n/2 times Time Complexity: O(n²) 🔄 Approach 2: Hash Map Use a dictionary to count frequencies Return element with count > n/2 💻 Code: ```python id="mj1" def majority_element(arr): freq = {} for num in arr: freq[num] = freq.get(num, 0) + 1 n