Majority Element II

You are given an array of integer arr[] where each number represents a vote to a candidate. Return the candidates that have votes greater than one-third of the total votes, If there’s not a majority vote, return an empty array. 

Note: The answer should be returned in an increasing format.

Examples:

Input: arr[] = [2, 1, 5, 5, 5, 5, 6, 6, 6, 6, 6]
Output: [5, 6]
Explanation: 5 and 6 occur more n/3 times.

Input: arr[] = [1, 2, 3, 4, 5]
Output: []
Explanation: no candidate occur more than n/3 times.

Constraint:
1 <= arr.size() <= 10⁶
-10⁹ <= arr[i] <= 10⁹

Approach 01:

#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;

class Solution {
public:
    // Function to find the majority elements in the array
    vector<int> findMajority(vector<int>& nums) {
        int n = nums.size();
        unordered_map<int, int> elementFrequency;
        vector<int> majorityElements;

        // Count the frequency of each element
        for (int num : nums) {
            elementFrequency[num]++;
        }

        // Check for elements that appear more than n/3 times
        for (const auto &it: elementFrequency) {
            if (it.second > n / 3) {
                majorityElements.push_back(it.first);
            }
        }

        // Sort the result
        sort(majorityElements.begin(), majorityElements.end());
        return majorityElements;
    }
};

import collections

class Solution:
    # Function to find the majority elements in the array
    def findMajority(self, nums):
        n = len(nums)
        elementFrequency = collections.Counter(nums)
        majorityElements = []
        for element, frequency in elementFrequency.items():
            if frequency > (n / 3):
                majorityElements.append(element)
        majorityElements.sort()
        return majorityElements

Time Complexity

• Frequency Count:

  Iterating through the array to populate the unordered_map for frequency counts takes \( O(n) \), where \( n \) is the size of the array.

• Majority Check:

  Iterating through the unordered_map to identify elements that appear more than \( n/3 \) times takes \( O(k) \), where \( k \) is the number of unique elements in the array.

• Sorting:

  Sorting the majority elements in the result takes \( O(m \log m) \), where \( m \) is the number of majority elements (usually small).

• Overall Time Complexity:

  The overall time complexity is \( O(n + k + m \log m) \). In most cases, \( k \) and \( m \) are much smaller than \( n \), so this simplifies to \( O(n) \).

Space Complexity

• Frequency Map:

  The unordered_map can store up to \( k \) unique elements, where \( k \) is the number of distinct elements in the array. This takes \( O(k) \) space.

• Majority Elements:

  The result vector stores up to \( m \) elements, where \( m \) is the number of majority elements. This takes \( O(m) \) space.

• Auxiliary Variables:

  Other variables such as n, num, and it take \( O(1) \) space.

• Overall Space Complexity:

  The overall space complexity is \( O(k + m) \), where \( k \) is the number of unique elements, and \( m \) is the number of majority elements.