DSA problem
Majority Element
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 in the array.
A hash map of counts solves this in linear time and linear space, but the optimal solution uses the Boyer-Moore Voting Algorithm to find the answer in linear time with only constant extra space.
Examples
Example 1
Input:
nums = [3,2,3]Output:
3Explanation: The value 3 appears twice, which is more than 3 / 2.
Example 2
Input:
nums = [2,2,1,1,1,2,2]Output:
2Explanation: The value 2 appears four times, which is more than 7 / 2.
Constraints
- n == nums.length
- 1 <= n <= 5 * 10^4
- -10^9 <= nums[i] <= 10^9
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.