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:
-
C++
-
Python
#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)\).