169. Majority Element

📝 Problem Details

• Title: 169. Majority Element
• Link: https://leetcode.com/problems/majority-element/
• Difficulty: Easy
• Tags/Categories: Sorting Arrays

💭What Were My Initial Thoughts?

- sort the input array
- return the element at n/2 position which is guaranteed to be the majority element

🤔What Did I Struggle With?

~

💡 Explanation of Solution

Sorting Solution:
	- sort the input array
	- return the element at n/2 position which is guaranteed to be the majority element

Hashmap Solution:
	- create a hashmap where the key is the number and the value is the frequency
	- if the frequency of a given number exceeds n/2, return that number

Boyer-Moore Voting Algorithm:
	- Traverse the array while maintaining a `count` and a `candidate`.
	- If `count` is 0, set the current element as the `candidate`.
	- If the current element matches the `candidate`, increment the `count`. Otherwise, decrement it.

⌛ Complexity Analysis

Sorting:
	Time Complexity: O(n log n) due to the use of comparison based sorting
	Space Complexity: O(1)

Hashmap:
	Time Complexity: O(n)
	Space Complexity: O(n) due to the auxilary space used to store frequencies in a map

Boyer-Moore:
	Time Complexity: O(n)
	Space Complexity: O(1)

💻 Implementation of Solution (Sorting)

class Solution {
 
public:
    int majorityElement(vector<int>& nums) {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        return nums[n/2];
    }
};

💻 Implementation of Solution (Hashmap)

int majorityElement(vector<int>& nums) {
    unordered_map<int, int> count;
    int n = nums.size();
    for (int num : nums) {
        count[num]++;
        if (count[num] > n / 2) {
            return num;
        }
    }
    return -1; // Should not reach here if majority element is guaranteed
}

💻 Implementation of Solution (Boyer-Moore)

int majorityElement(vector<int>& nums) {
    int candidate = nums[0], count = 0;
    for (int num : nums) {
        if (count == 0) {
            candidate = num;
        }
        count += (num == candidate) ? 1 : -1;
    }
    return candidate; // No need to verify if a majority is guaranteed
}