Majority Element

Problem

Given an array nums of size n, return the majority element.

The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists.

Input / Output Format

Input: Array nums. Output: The majority element.

Examples

Example 1

Input: nums = [3,2,3] → Output: 3

Example 2

Input: nums = [2,2,1,1,1,2,2] → Output: 2

Approach Hints

• Boyer-Moore Voting Algorithm (optimal) — Maintain candidate and count = 0. Iterate: if count == 0, set candidate = num. If num == candidate, count++ else count--. After full pass, candidate is the majority. Time: O(n), Space: O(1).
• Hash Map — Count occurrences, return key with count > n/2. O(n) time, O(n) space.
• Sorting — nums[n/2] is the answer. O(n log n).
• Boyer-Moore works because the majority element survives the cancellation of non-majority elements.