Majority Element

Problem Statement Given an array arr[], find the majority element in the array. A majority element is an element that appears strictly more than arr.size()/2 times. If no majority element exists, return -1. Examples Input: arr = [1, 1, 2, 1, 3, 5, 1] Output: 1 Explanation: 1 appears more than 7/2 = 3.5 times. Input: arr = [7] Output: 7 Explanation: Single element is trivially the majority. Input: arr = [2, 13] Output: -1 Explanation: No element appears more than 2/2 = 1 times. Constraints 1 ≤ arr.size() ≤ 10^5 1 ≤ arr[i] ≤ 10^5 Approach 1: Using Hash Map Count the frequency of each element using a dictionary. If an element count exceeds n//2, return it. Time Complexity: O(n) Space Complexity: O(n) from typing import List class Solution: def majorityElement(self, arr: List[int]) -> int: n = len(arr) freq = {} for num in arr: freq[num] = freq.get(num, 0) + 1 if freq[num] > n // 2: return num return -1 Approach 2: Boyer-Moore Voting Algorithm The Boyer-Moore Voting Algorithm allows