Ashish PrajapatiWhat I learned?
I learned the following topics:
- Moose’s Voting Algorithm
What I developed/solved?
- Solved leetcode problem 169. Majority Element usiing *
Code snippet/Screenshots/notes
- Leetcode 169. Majority Element
- Problem Statement: Given an array
numsof sizen, return the majority element. - The majority element is the element that appears more than
⌊n / 2⌋times. - Example.
Input: nums = [3,2,3]
Output: 3
Input: nums = [2,2,1,1,1,2,2]
Output: 2
- Better solution using Hashmaps
int n = nums.size();
int ans = 0;
int appears = (n/2);
map<int, int>m;
//store every element's occurance
for(int i = 0; i<nums.size(); i++){
m[nums[i]]++;
}
//element occurs more than (n/2) times, will be our final answer
for(auto it:m){
if(it.second > appears){
ans = it.first;
}
}
return ans;
//Time complexity: O(n) + O(n*logN)
//Space complexity: O(n) --> worst case when all elements are unique
- Optimal Solution using Moose’s Voting Algorithm
class Solution {
public:
int majorityElement(vector<int>& nums) {
int n = nums.size();
int element = nums[0];
int cnt = 1;
for (int i = 1; i < n; i++) {
if (nums[i] != element) {
cnt--;
if (cnt == 0) {
i++;
element = nums[i];
cnt = 1;
}
} else {
cnt++;
}
}
cnt = 0;
for(auto it:nums){
if(it == element){
cnt++;
}
}
if(cnt > (n/2)){
return element;
}
else{
return -1;
}
}
};
// Time complexity: O(n) + O(n) ~ O(2*n) = 0(n)
// Space Comlexity: O(1) as we are not using extra space
- Boyer-moore Voting Algorithm
