11. Majority Element
Given an array nums of length n, return its majority element: the value that occurs more than n / 2 times (strictly more than half of the array).
Every test is guaranteed to have a majority element.
Input: nums = [5,1,5] Output: 5
Explanation: 5 appears twice out of three elements.
Input: nums = [4,7,7,4,7,7,4] Output: 7
Explanation: 7 appears 4 times, which is more than 7 / 2 = 3.5.
Input: nums = [9] Output: 9
Constraints
1 <= nums.length <= 5 * 10^4-10^9 <= nums[i] <= 10^9- A majority element always exists.
Follow-up: Can you solve it in linear time using only O(1) extra space?
💡 Hint 1
Counting occurrences in a hash map is O(n) time but O(n) space. Sorting also works: which index must the majority element occupy after sorting?
💡 Hint 2
For O(1) space, pair up each occurrence of the majority value with a different value and cancel them out. Since it fills more than half the array, something of it survives.
💡 Hint 3
Keep a candidate and a count: when count is 0, adopt the current value; add 1 when you see the candidate and subtract 1 otherwise.
Try it yourself first ✎
Solutions stick better after a real attempt. Peek when you're ready.
Approach
Use the Boyer-Moore voting idea. Keep a candidate and a count. When count is 0, the current value becomes the candidate. Each occurrence of the candidate adds a vote and every other value removes one. Every removal cancels one majority occurrence against one non-majority occurrence at most, and the majority value has more occurrences than all other values combined, so it is the candidate left standing at the end.
function majorityElement(nums) {
let candidate = 0;
let count = 0;
for (const x of nums) {
if (count === 0) candidate = x;
count += x === candidate ? 1 : -1;
}
return candidate;
}class Solution {
public int majorityElement(int[] nums) {
int candidate = 0, count = 0;
for (int x : nums) {
if (count == 0) candidate = x;
count += (x == candidate) ? 1 : -1;
}
return candidate;
}
}No submissions yet. Press Submit to run your code against every test.
/**
* @param {number[]} nums
* @return {number}
*/
function majorityElement(nums) {
}Run your code to see results here.