What 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
Top comments (0)