Day 9 of #100DaysOfCode | 31-03-2024

#100daysofcode #cpp #dsa

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 nums of size n, 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