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

There are several ways to solve this problem. We'll explore two efficient approaches:

Approach 1: Hash Map (Unordered Map)

1. Create a hash map: Use an unordered_map to store each element in nums as a key and its count as the value.
2. Iterate and count: Iterate through the array. For each element, increment its count in the hash map.
3. Find the majority: After iterating, iterate through the hash map and find the element with a count greater than n / 2.

Approach 2: Boyer-Moore Voting Algorithm

This algorithm is remarkably efficient. It leverages the fact that the majority element appears more than half the time.

1. Initialize: Start with a candidate element (initially the first element) and a count (initialized to 1).
2. Iterate: Iterate through the array, starting from the second element.
   • If the current element is the same as the candidate, increment count.
   • If the current element is different from the candidate:
     • Decrement count.
     • If count becomes 0, replace the candidate with the current element and reset count to 1.
3. Return: After iterating, the candidate will be the majority element. (A final check isn't strictly necessary since the problem states the majority element always exists).

Explanation

Approach 1 (Hash Map): This approach is straightforward but uses extra space proportional to the number of unique elements in the array.

Approach 2 (Boyer-Moore): This is a linear time and constant space solution. The intuition is that when you encounter a different element, you cancel out a count of the candidate. If the candidate is truly the majority element, it will survive these cancellations.

Code (C++)

#include <iostream>
#include <unordered_map>
#include <vector>

class Solution {
public:
    // Approach 1: Hash Map
    int majorityElementHashMap(std::vector<int>& nums) {
        std::unordered_map<int, int> counts;
        for (int num : nums) {
            counts[num]++;
        }
        int n = nums.size();
        for (auto const& [key, val] : counts) {
            if (val > n / 2) {
                return key;
            }
        }
        return -1; // Should not reach here based on problem constraints
    }

    //Approach 2: Boyer-Moore Voting Algorithm
    int majorityElementBoyerMoore(std::vector<int>& nums) {
        int candidate = nums[0];
        int count = 1;
        for (size_t i = 1; i < nums.size(); ++i) {
            if (nums[i] == candidate) {
                count++;
            } else {
                count--;
                if (count == 0) {
                    candidate = nums[i];
                    count = 1;
                }
            }
        }
        return candidate;
    }
};

int main() {
    std::vector<int> nums1 = {3, 2, 3};
    std::vector<int> nums2 = {2, 2, 1, 1, 1, 2, 2};
    Solution sol;
    std::cout << "Majority element (HashMap): " << sol.majorityElementHashMap(nums1) << std::endl; // Output: 3
    std::cout << "Majority element (HashMap): " << sol.majorityElementHashMap(nums2) << std::endl; // Output: 2
    std::cout << "Majority element (Boyer-Moore): " << sol.majorityElementBoyerMoore(nums1) << std::endl; // Output: 3
    std::cout << "Majority element (Boyer-Moore): " << sol.majorityElementBoyerMoore(nums2) << std::endl; // Output: 2

    return 0;
}

Complexity

Approach 1 (Hash Map):

• Time Complexity: O(n), where n is the length of the input array. We iterate through the array once to count elements and then iterate through the hash map (which in the worst case could be of size n).
• Space Complexity: O(k), where k is the number of unique elements in the array. This can be at most O(n) in the worst case.

Approach 2 (Boyer-Moore Voting Algorithm):

• Time Complexity: O(n) – A single pass through the array.
• Space Complexity: O(1) – Constant extra space is used. No additional data structures that scale with input size are needed.