Majority Element
Problem
Given an array
nums
of sizen
, 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.
Example 1:
Input: nums = [3,2,3] Output: 3
Example 2:
Input: nums = [2,2,1,1,1,2,2] Output: 2
Pseudocode
make a map of unique numbers and the number of occurances, return majority element immediately if > n / 2 is found
Solution
var majorityElement = function (nums) {
const len = nums.length;
const map = {};
for (let i = 0; i < len; i++) {
if (!map[nums[i]]) {
map[nums[i]] = 0;
}
map[nums[i]]++;
if (map[nums[i]] > len / 2) {
return nums[i];
}
}
};
Time and Space Complexity
Time
Loop through array once to find unique numbers and their counts - O(N)
Total - O(N)
Space
Storing a map of unique numbers and their counts - O(N)
Total - O(N)
Last updated