Majority Element

Leetcode Problem 169: Majority Element

Problem Summary

Given an array nums of size n, 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.

Techniques

• Boyer-Moore Voting Algorithm
• Linear time complexity
• Constant space complexity

Solution

function majorityElement(nums: number[]): number {
    let candidate = 0;
    let count = 0;

    for (const num of nums) {
        if (count === 0) {
            candidate = num;
        }
        count += (num === candidate) ? 1 : -1;
    }

    count = 0;

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

    if (count > nums.length / 2) {
        return candidate;
    } else {
        return -1
    }
}

const test = [2, 2, 1, 1, 1, 2, 2];
console.log(majorityElement(test))