i was trying to solve this problem on leetcode.
Majority Element – LeetCode
Given an array
numsof sizen, return the majority element.The majority element is the element that appears more than
⌊n / 2⌋times. You may assume that the majority element always exists in the array.
Input: nums = [3,2,3]
Output: 3
Input: nums = [2,2,1,1,1,2,2]
Output: 2
but i wrote the solution and i am getting memory limit exceeded and i dont know why can you please help me with this?
class Solution {
public:
int majorityElement(vector<int>& nums) {
unordered_map<long long,int>hash;
for(int i = 0; i<nums.size(); i++)
{
hash[nums[i]]++;
}
for(int i = 0;i<hash.size();i++)
{
if(hash[i]>(nums.size()/2))
return i;
}
return -1;
}
};
9
The reason you are running out of memory is because the hash map grows indefinitely. This is due to the way you are trying to loop though the map.
Accessing map values with the square brackets like hash[i] adds a new key if the key does not exist yet. This increases the size of the map meaning that i<hash.size() never becomes false and your loop won’t terminate until the map is so big you start running into memory issues.
Looping through a map can be done as follows:
for (auto it = hash.begin(); it != hash.end(); it++) {
it->first // key
it->second // value
}
// Or
for (auto&& [key,value] : hash) { }
2
The whole idea of this task is not to use containers at all. That is why memory limit in this task is lowered.
There is algorithm called “heavy hitter” (generalization of Boyer-Moore_majority_vote_algorithm) which can solve this task in O(n) time and with O(1) memory complexity. This is also why the task description is so strange:
Majority Element – LeetCode
Given an array
numsof sizen, return the majority element.The majority element is the element that appears more than
⌊n / 2⌋times. You may assume that the majority element always exists in the array.