Majority Element

Introduction Finding the most frequent element in an array might seem simple, but doing it efficiently is the real challenge. This problem introduces a powerful technique called the Boyer-Moore Voting Algorithm, which solves it in linear time and constant space. Problem Statement Given an array arr, find the majority element. A majority element is one that appears more than n/2 times. If it exists → return the element If not → return -1 Example 1 Input: ```python id="z1mqz9" arr = [1, 1, 2, 1, 3, 5, 1] Output: ```python id="sdif4r" 1 Example 2 Input: ```python id="q3m2zx" arr = [7] Output: ```python id="d9q2k3" 7 Example 3 Input: ```python id="v2g9bn" arr = [2, 13] Output: ```python id="l0w7fp" -1 Brute Force Approach Count frequency of each element Return element with count > n/2 Time Complexity: O(n²) Better Approach (Hash Map) Use a dictionary to count frequencies Time Complexity: O(n) Space Complexity: O(n) Optimal Approach: Boyer-Moore Voting Algorithm Key Idea Maintain: candid