Finding the Majority Element (Appearing More than n/2 Times)

Introduction

Finding the majority element in an array is a classic problem in coding interviews and competitive programming. The majority element is the element that appears more than n/2 times, where n is the size of the array.

We will explore three approaches to solving this problem:

1. Brute Force - O(n²) time complexity

2. Better Approach (Hashing) - O(n log n) + O(n) time complexity

3. Optimal Approach (Moore’s Voting Algorithm) - O(n) time complexity

You can find the problem statement here: https://leetcode.com/problems/majority-element/description/

---

Brute Force Approach (O(n²))

Idea:

• We pick each element and count its occurrences by scanning the array.

• If an element occurs more than n/2 times, it is the majority element.

• This results in a time complexity of O(n²).

Code Implementation:

#include <iostream>
using namespace std;

int findMajorityElement(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        int count = 0;
        for (int j = 0; j < n; j++) {
            if (arr[j] == arr[i])
                count++;
        }
        if (count > n / 2)
            return arr[i];
    }
    return -1; // No majority element found
}

int main() {
    int arr[] = {7, 7, 5, 7, 5, 1, 5, 7, 5, 5, 7, 7, 5, 5, 5, 5};
    int n = sizeof(arr) / sizeof(arr[0]);

    int majorityElement = findMajorityElement(arr, n);
    if (majorityElement != -1)
        cout << "Majority Element: " << majorityElement << endl;
    else
        cout << "No Majority Element found" << endl;

    return 0;
}

Complexity Analysis:

• Time Complexity: O(n²)

• Space Complexity: O(1)

---

Better Approach: Hashing (O(n log n) + O(n))

Idea:

• Use a hash table to store the frequency of each element.

• Traverse the hash table to find the element with frequency greater than n/2.

• This reduces the time complexity to O(n log n) + O(n).

Code Implementation:

#include <iostream>
#include <unordered_map>
using namespace std;

int findMajorityElement(int arr[], int n) {
    unordered_map<int, int> freq;

    for (int i = 0; i < n; i++)
        freq[arr[i]]++; // Count frequency of each element

    for (auto &it : freq) {
        if (it.second > n / 2)
            return it.first;
    }
    return -1; // No majority element found
}

int main() {
    int arr[] = {7, 7, 5, 7, 5, 1, 5, 7, 5, 5, 7, 7, 5, 5, 5, 5};
    int n = sizeof(arr) / sizeof(arr[0]);

    int majorityElement = findMajorityElement(arr, n);
    if (majorityElement != -1)
        cout << "Majority Element: " << majorityElement << endl;
    else
        cout << "No Majority Element found" << endl;

    return 0;
}

Complexity Analysis:

• Time Complexity: O(n log n) + O(n)

• Space Complexity: O(n)

---

Optimal Approach: Moore’s Voting Algorithm (O(n))

Idea:

• This algorithm works in two steps:

  1. Find a candidate that might be the majority element using the Boyer-Moore voting technique.

  2. Verify if the candidate is actually the majority element by counting its occurrences.

• The algorithm efficiently finds the majority element in O(n) time with O(1) space.

Code Implementation:

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int n=nums.size(),majorityEle;
        int count=0;
        for(int i=0;i<n;i++)
        {
            if(count==0)
            {
                majorityEle=nums[i];
                count=1;
            }
            else if(nums[i]==majorityEle)
            count++;
            else
            count--;
        }
        for(int i=0;i<n;i++)
        {
            if(nums[i]==majorityEle)
            {
                count++;
            }
            if(count>(n/2))
            {
                return majorityEle;
            }
        }
        return -1;
    }
};

Complexity Analysis:

• Time Complexity: O(n)

• Space Complexity: O(1)

---

Final Thoughts

• Brute Force: Easy to implement but inefficient.

• Hashing: Improves performance but requires extra space.

• Moore’s Voting Algorithm: Most optimal, runs in O(n) time and O(1) space.

For large datasets, Moore’s Voting Algorithm is the best choice. Hope this blog helps you understand the problem and its solutions better! 🚀

Let me know if you have any questions in the comments. Happy Coding! 😊