Majority Element

Given an array of n integers, find the majority element: the value that appears strictly more than n/2 times. It is guaranteed that the array always contains such an element.

Input: The first line contains a single integer n. The second line contains n space-separated integers. Output: A single integer: the majority element.

1 <= n <= 10^5. -10^9 <= arr[i] <= 10^9. A majority element (appearing more than n/2 times) is guaranteed to exist.

Because a majority element is explicitly GUARANTEED to exist here, there's no need for BOYER-MOORE's extra verification pass - a plain counting hash map is sufficient and arguably simpler to get right, at the cost of O(n) space instead of O(1).

Find the value that appears strictly more than half the time in an array, using a hash map. Brute force: For every distinct value, scan the whole array counting its occurrences directly - this costs O(n²) in the worst case if there are many distinct values, unnecessary when a single hash-map pass counts everything at once. Optimised: A hash map lets every value's running count be updated and checked in O(1) per element, finding the guaranteed majority element in a single linear pass - no need for a second verification pass here, since the problem explicitly GUARANTEES a majority element exists (unlike the more general Boyer-Moore voting version, which needs a verification step precisely because it does NOT assume one exists).

1. Scan the array once, using a hash map to count how many times each value has appeared so far. 2. The moment any value's running count exceeds n/2, that value is the answer - the problem guarantees one exists.

Time: O(n) - one single pass, with O(1) average-case hash map operations. Space: O(n) in the worst case, for the hash map of value counts.

When n = 1, the single element is trivially the majority element. The majority element need not be at the start of the array.

Be ready to contrast this hash-map approach with the O(1)-space Boyer-Moore voting algorithm (covered elsewhere for the general case without a guarantee) - the hash-map version trades extra space for being simpler to reason about and implement correctly under time pressure.