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() ≤ 105
0 ≤ arr[i] ≤ 105


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)\).

Leave a Comment

Your email address will not be published. Required fields are marked *

Scroll to Top