Majority Element

Problem Statement

Constraints

Solution 1: Boyer-Moore Voting Algorithm

function majorityElementBoyer(nums) {
    let candidate = null;
    let count = 0;

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

    return candidate;
} 

const nums1 = [3, 2, 3];
majorityElementBoyer(nums1);  //output: 3 

const nums2 = [2, 2, 1, 1, 1, 2, 2];
majorityElementBoyer(nums2);  //output: 2 

Solution 2: Hash Map Approach

function majorityElementHashMap(nums) {
    const counts = new Map();

    for (const num of nums) {
        counts.set(num, (counts.get(num) || 0) + 1);
        if (counts.get(num) > nums.length / 2) {
            return num;
        }
    }
} 

const nums1 = [3, 2, 3];
majorityElementHashMap(nums1);  //output: 3 

const nums2 = [2, 2, 1, 1, 1, 2, 2];
majorityElementHashMap(nums2);  //output: 2 

Solution 3: Sorting Approach

function majorityElementSorting(nums) {
    nums.sort((a, b) => a - b);
    return nums[Math.floor(nums.length / 2)];
} 

const nums1 = [3, 2, 3];
majorityElementSorting(nums1);  //output: 3 

const nums2 = [2, 2, 1, 1, 1, 2, 2];
majorityElementSorting(nums2);  //output: 2 

Solution 4: Divide and Conquer Approach

function majorityElementDivideConquer(nums) {
    function majorityElementRec(start, end) {
        if (start === end) {
            return nums[start];
        }
        
        const mid = Math.floor((start + end) / 2);
        const left = majorityElementRec(start, mid);
        const right = majorityElementRec(mid + 1, end);

        if (left === right) {
            return left;
        }

        const leftCount = nums.slice(start, end + 1).filter(x => x === left).length;
        const rightCount = nums.slice(start, end + 1).filter(x => x === right).length;

        return leftCount > rightCount ? left : right;
    }

    return majorityElementRec(0, nums.length - 1);
} 

const nums1 = [3, 2, 3];
majorityElementDivideConquer(nums1);  //output: 3 

const nums2 = [2, 2, 1, 1, 1, 2, 2];
majorityElementDivideConquer(nums2);  //output: 2 

Solution 5: Naive Approach

function majorityElement(nums) {
    for (let i = 0; i < nums.length; i++) {
        let count = 0;
        for (let j = 0; j < nums.length; j++) {
            if (nums[j] === nums[i]) {
                count++;
            }
        }
        if (count > nums.length / 2) {
            return nums[i];
        }
    }
} 

const nums1 = [3, 2, 3];
majorityElement(nums1);  //output: 3 

const nums2 = [2, 2, 1, 1, 1, 2, 2];
majorityElement(nums2);  //output: 2 

Solution 6: Using a Counter Object

function majorityElementCounterObj(nums) {
    const count = {};
    const majorityCount = nums.length / 2;

    for (const num of nums) {
        count[num] = (count[num] || 0) + 1;
        if (count[num] > majorityCount) {
            return num;
        }
    }
} 

const nums1 = [3, 2, 3];
majorityElementCounterObj(nums1);  //output: 3 

const nums2 = [2, 2, 1, 1, 1, 2, 2];
majorityElementCounterObj(nums2);  //output: 2 

Solution 7: Bit Manipulation Approach

function majorityElementBitManipulation(nums) {
    const majorityCount = nums.length / 2;
    const bitLength = 32; // Assume 32-bit integers

    let majority = 0;

    for (let bit = 0; bit < bitLength; bit++) {
        let count = 0;
        for (const num of nums) {
            if ((num & (1 << bit)) !== 0) {
                count++;
            }
        }
        if (count > majorityCount) {
            majority |= (1 << bit);
        }
    }

    return majority;
} 

const nums1 = [3, 2, 3];
majorityElementBitManipulation(nums1);  //output: 3 

const nums2 = [2, 2, 1, 1, 1, 2, 2];
majorityElementBitManipulation(nums2);  //output: 2 

Solution 8: Using Priority Queue

function majorityElementPriorityQueue(nums) {
    const count = new Map();
    const majorityCount = nums.length / 2;
    
    // Count occurrences of each number
    for (const num of nums) {
        count.set(num, (count.get(num) || 0) + 1);
    }
    
    // Use a priority queue to find the majority element
    const minHeap = [];
    
    count.forEach((value, key) => {
        minHeap.push({key, value});
    });
    
    minHeap.sort((a, b) => b.value - a.value); // Sort by frequency in descending order
    
    return minHeap[0].key; // Return the majority element
} 

const nums1 = [3, 2, 3];
majorityElementPriorityQueue(nums1);  //output: 3 

const nums2 = [2, 2, 1, 1, 1, 2, 2];
majorityElementPriorityQueue(nums2);  //output: 2 

Solution 9: Randomized Approach

function majorityElementRandomized(nums) {
    function findMajority(candidate, nums) {
        let count = 0;
        for (const num of nums) {
            if (num === candidate) {
                count++;
            }
        }
        return count > nums.length / 2;
    }
    
    let candidate;
    while (true) {
        candidate = nums[Math.floor(Math.random() * nums.length)];
        if (findMajority(candidate, nums)) {
            return candidate;
        }
    }
} 

const nums1 = [3, 2, 3];
majorityElementRandomized(nums1);  //output: 3 

const nums2 = [2, 2, 1, 1, 1, 2, 2];
majorityElementRandomized(nums2);  //output: 2 

More Problems Solutions