Arrays & Hashing · 101Easy
Majority Element
Given an array nums of size n, return the element that appears more than n/2 times. You may assume a majority element always exists.
Constraints
- n == nums.length, 1 <= n <= 5 * 10^4
- -10^9 <= nums[i] <= 10^9
- A majority element is guaranteed to exist.
Examples
majorityElement([3, 2, 3]) -> 3 majorityElement([2, 2, 1, 1, 1, 2, 2]) -> 2 majorityElement([1]) -> 1 // single element majorityElement([6, 5, 5]) -> 5 // smallest non-trivial majority majorityElement([-1, -1, 2]) -> -1 // negatives are valid majorityElement([2, 2, 1, 1, 2]) -> 2 // 3 of 5 is a majority
Edge cases
- A single element is trivially the majority.
- 'More than n/2' is strict — exactly half does not qualify.
Show the target complexity (spoiler)
- Naive
- O(n) time, O(n) space — count every value in a hash map and take the largest count.
- Target
- O(n) time, O(1) space — Boyer-Moore voting: keep a candidate and a counter, resetting the candidate whenever the counter hits zero.
Solve it
By hand, in your editor. The runner checks answers and timing.
git clone https://github.com/sarmadkung/optimal-round cd optimal-round # open problems/01-arrays-hashing/101-majority-element.js ./practice c 101