Majority Element easy

Problem Statement

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.

Example 1:

Input: nums = [3,2,3] Output: 3

Example 2:

Input: nums = [2,2,1,1,1,2,2] Output: 2

Steps to Solve

We can solve this problem using several approaches. Here, we'll explore two efficient methods:

1. Hash Map (Frequency Counting): Iterate through the array, storing the frequency of each element in a hash map. Then, find the element with the highest frequency.

2. Boyer-Moore Voting Algorithm: This algorithm is highly efficient in terms of space complexity. It leverages the fact that the majority element appears more than half the time. We maintain a candidate element and a count. If we encounter the candidate, we increment the count; otherwise, we decrement it. If the count reaches zero, we change the candidate to the current element. At the end, the candidate will be the majority element.

Explanation

Hash Map Approach: This approach is straightforward. We use a hash map (object in JavaScript/TypeScript) to count the occurrences of each number. After iterating through the array, we iterate through the hash map to find the element with the highest count. This guarantees finding the majority element.

Boyer-Moore Voting Algorithm: This approach is more subtle. The algorithm works because the decrements caused by elements other than the majority element will eventually cancel out with increments caused by the majority element itself. Therefore, the remaining element after this process will be the majority element.

Code (TypeScript)

function majorityElement(nums: number[]): number {
    // Hash Map Approach
    const counts: { [key: number]: number } = {};
    for (const num of nums) {
        counts[num] = (counts[num] || 0) + 1;
    }
    let majorityElement = -1;
    let maxCount = 0;
    for (const num in counts) {
        if (counts[parseInt(num)] > maxCount) {
            maxCount = counts[parseInt(num)];
            majorityElement = parseInt(num);
        }
    }
    return majorityElement;

    // Boyer-Moore Voting Algorithm (Alternative)
    // let candidate = nums[0];
    // let count = 1;
    // for (let i = 1; i < nums.length; i++) {
    //     if (nums[i] === candidate) {
    //         count++;
    //     } else {
    //         count--;
    //         if (count === 0) {
    //             candidate = nums[i];
    //             count = 1;
    //         }
    //     }
    // }
    // return candidate;
}

Complexity

Hash Map Approach:

• Time Complexity: O(n), where n is the length of the input array. We iterate through the array once to count frequencies and again to find the maximum.
• Space Complexity: O(n) in the worst case (if all elements are unique).

Boyer-Moore Voting Algorithm:

• Time Complexity: O(n) - Single pass through the array.
• Space Complexity: O(1) - Constant extra space. It uses only a few variables to store the candidate and its count.

The Boyer-Moore algorithm is generally preferred due to its superior space complexity, especially for large input arrays. The hash map approach is easier to understand, though. The code above provides both implementations, with the hash map approach uncommented and the Boyer-Moore approach commented out. You can uncomment the Boyer-Moore section to run that algorithm instead.