Is it possible to do in O(1) time complexity ?
There are multiple ways to solve this problem
One way is to sort the elements and return the middle element in array
Since the question says the majority element is more than n/2 times
the mid element has to be the majority element after sort
but the time complexity of this approach is O(nlogn) since we are sorting
Another way is to create a hashmap where key is the element and value is the times it is present in array
but the time complexity of this approach as well won't be O(1)
Now let's go into the solution with O(1) complexity
Boyer–Moore majority vote algorithm
/**
* @param {number[]} nums
* @return {number}
*/
var majorityElement = function(nums) {
let count = 1 ;
let res = nums[0] ;
for(let i = 1 ; i<nums.length ;i++){
if(count==0){
res = nums[i]
}
if(nums[i] == res){
count++
}else{
count--;
}
}
return res;
};
Result
Top comments (0)