Leetcode: 169. Majority Element (Hash Table)

Majority Element

In this blog post, we will explore an interesting algorithmic problem: finding the majority element in an array. We will discuss an efficient approach to solve this problem and analyze its complexity. Let's get started!

Problem Statement

Given an array nums of size n, our task is to find the majority element, which is the element that appears more than ⌊n / 2⌋ times in the array. We can assume that the majority element always exists in the array.

Approach

We can solve this problem using a counting algorithm. The idea is to iterate through the array and keep track of the count of each element using an unordered map. The key of the map will be the element, and the value will be the count of occurrences of that element.

To find the majority element, we will maintain a pair to store the element with the highest count encountered so far. We initialize the majority entry with a count of 0 and then update it whenever we find an element with a higher count than the current majority entry.

Let's analyze the complexity of our solution:

• Time Complexity: The countNums function iterates through the entire array once, which takes O(n) time, where n is the size of the array. The subsequent loop in the majorityElement function iterates through the map, which takes O(m) time, where m is the number of unique elements in the array (m <= n). Thus, the overall time complexity is O(n + m). Since the majority element will always appear more than n / 2 times, m will be at most n / 2, making the time complexity effectively O(n).
• Space Complexity: We use an unordered map to store the count of each element, which can have a maximum of n unique keys. Therefore, the space complexity is O(n).

Code Example

Below is the C++ code implementation of the solution:

class Solution {
private:
    std::unordered_map<int, int> countNums(std::vector<int>& nums) {
        std::unordered_map<int, int> counts;
        for (int num : nums) {
            if (counts.find(num) == counts.end()) {
                counts[num] = 1;
            }
            else {
                counts[num]++;
            }
        }
        return counts;
    }

public:
    int majorityElement(std::vector<int>& nums) {
        std::unordered_map<int, int> counts = countNums(nums);

        std::pair<int, int> majorityEntry;
        for (const auto& entry : counts) {
            if (majorityEntry.first == 0 || entry.second > majorityEntry.second) {
                majorityEntry = entry;
            }
        }

        return majorityEntry.first;
    }
};

With this implementation, you can now easily find the majority element in the given array using the provided function majorityElement().

Example

Let's take an example to understand the function's usage:

// Input:
vector<int> nums = {2, 2, 1, 1, 1, 2, 2};

// Output:
Solution solution;
int majority = solution.majorityElement(nums);
// The output should be: 2

By using the provided function with the given input, you can find the majority element and obtain the output as mentioned in the example above.

I hope you found this blog post helpful in understanding the Majority Element problem and its solution. Happy coding!