Solution

• Problem first got me thinking that we can have 2 or more types of elements like [1,2,3,3]. But turned out array can only contain two different numbers. This simplified the task. Used algorithm is called Moore’s voting algorithm.

function majorityElement(nums: number[]): number {
    let count = 0;
    let candidate = 0;
    for(let i = 0; i < nums.length; i++){
        if(count === 0){
            candidate = nums[i];
            count = 1;
        }else{
            const modifier = nums[i] === candidate ? 1 : -1;
            count = count + modifier;
        }
    }

    return candidate;
};

Performance

• Runtime - O(n) (beats 88%)
• Memory - O(1) beats 80%