singularity

singularity 🔎

169. Majority element

O(n log n)

if(nums.length < 3) return nums[0]
nums.sort((a,b)=>a-b);
return nums[Math.floor((nums.length)/2)]

O(n) space and O(n) time

let hm = {}
let max = -1;
let i = 0;

for(n of nums){
    hm[n] = hm[n]+1 || 1
}

Object.entries(hm).forEach(k => {
    if(k[1] > max){
        max = k[1]
        i = k[0]
    }
})

return i;

O(1) space and O(n) time, Boyer-Moore majority voting

let candidate;
let count = 0;
for (const num of nums) {
    if (count === 0) {
        candidate = num;
    }

    count += (num === candidate) ? 1 : -1
}

return candidate;