Majority Element

Given an array arr[]. Find the majority element in the array. If no majority element exists, return -1.

Note: A majority element in an array is an element that appears strictly more than arr.size()/2 times in the array.

Examples:

Input: arr[] = [1, 1, 2, 1, 3, 5, 1]
Output: 1
Explanation: Since, 1 is present more than 7/2 times, so it is the majority element.

Input: arr[] = [7]
Output: 7
Explanation: Since, 7 is single element and present more than 1/2 times, so it is the majority element.

Input: arr[] = [2, 13]
Output: -1
Explanation: Since, no element is present more than 2/2 times, so there is no majority element.

Constraints:
1 ≤ arr.size() ≤ 10⁵
0 ≤ arr[i] ≤ 10⁵

Approach 01:

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

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        unordered_map<int, int> frequencyMap;
        int arraySize = nums.size();

        for (int num : nums)
            ++frequencyMap[num];

        for (const auto& [element, count] : frequencyMap)
            if (count > arraySize / 2)
                return element;

        return -1;
    }
};

class Solution:
    def majorityElement(self, nums):
        frequencyMap = {}
        arraySize = len(nums)

        for num in nums:
            frequencyMap[num] = frequencyMap.get(num, 0) + 1

        for element, count in frequencyMap.items():
            if count > arraySize // 2:
                return element

        return -1

Time Complexity:

• Building Frequency Map:

  Iterates over all elements → \(O(n)\).

• Checking Majority:

  Iterates over unique elements (at most \(n\)) → \(O(n)\) in the worst case.

• Total Time Complexity:

  \(O(n)\).

Space Complexity:

• Hash Map:

  Stores frequency of each element → \(O(n)\) in the worst case (all elements distinct).

• Total Space Complexity:

  \(O(n)\).