हिन्दी flagहिन्दी  
CLOSE

Suggested:

🛠️ Settings

Problem Statement

Given an integer array nums of size n, return the majority element of the array.

The majority element of an array is an element that appears more than n/2 times in the array. The array is guaranteed to have a majority element.

LeetCode:

Examples

Example 1:

Input: nums = [7, 0, 0, 1, 7, 7, 2, 7, 7]
Output: 7

Explanation: The array is of size 9, and the element 7 appears 5 times.
Example 2:

Input: nums = [1, 1, 1, 2, 1, 2]
Ouput: 1

Explanation: The array is of size 6, and the element 1 appears 4 times.
Example 3:

Input: nums = [2, 2, 1, 1, 1, 2, 2]
Output: 2

Explanation: The array is of size 7, Majority threshold is 3.5, so element must appear 4 or more than 4 times. The number 2 appears 4 times.

Constraints:

n == nums.length.
1 <= n <= 10^5
-10^4 <= nums[i] <= 10^4
One value appears more than n/2 times.

Different Approaches

1️⃣ Brute Force Approach (Nested Loop)

Intuition:

Naive way is to count the occurrences of each element. The element which will have count greater than half the array size will be the majority element.

Approach:

  1. Iterate in the array to select the elements of the array one by one. Now, for each element, run another loop and count its occurrence in the given array.
  2. If any element occurs more than the floor of (N/2), simply return it.

Code:

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    // Function to find the majority element in an array
    int majorityElement(vector<int>& nums) {
        
        // Size of the given array
        int n = nums.size();
        
        // Iterate through each element of the array
        for (int i = 0; i < n; i++) {
            
            // Counter to count occurrences of nums[i]
            int cnt = 0; 
            
            // Count the frequency of nums[i] in the array
            for (int j = 0; j < n; j++) {
                if (nums[j] == nums[i]) {
                    cnt++;
                }
            }
            
            // Check if frequency of nums[i] is greater than n/2
            if (cnt > (n / 2)) {
                // Return the majority element
                return nums[i]; 
            }
        }
        
        // Return -1 if no majority element is found
        return -1; 
    }
};

int main() {
    vector<int> arr = {2, 2, 1, 1, 1, 2, 2};
    
    // Create an instance of Solution class
    Solution sol;
 
    int ans = sol.majorityElement(arr);
    
    // Print the majority element found
    cout << "The majority element is: " << ans << endl;
    
    return 0;
}

Complexity Analysis:

  • Time Complexity:O(N^2), for nested for loops used, where N is the size of the array
  • Space Complexity:O(1) as no extra space is used.

2️⃣ HashMap Approach

Intuition:

The idea is to use a better data structure to reduce the number of look-up operations and hence the reducing the time complexity. Moreover, we have been calculating the count of the same element again and again, so try to reduce that also.

Approach:

  1. Use a hashmap and store as (key, value) pairs. Here the key will be the element of the array and the value will be the number of times it occurs.
  2. Traverse the array and update the value of the key. Simultaneously check if the value is greater than the floor of N/2. If yes, return the key, otherwise iterate forward.

Why unordered_map instead of array for the frequncy count?

We use the array for the frequency count, when we know the numbers are small and non-negative like:

nums = [0, 1, 2, 2, 1, 0]

Then we can use a simple array:

int count[3] = {0}; // for values 0 to 2

But if we have:

nums = [999999999, -234, 12, ...]

Then an array like count[100000000000] is impossible – too big and can't handle negatives.

So in such cases:

unordered_map<int, int> count;

is safe, dynamic, and handles all type of integers.

Featureunordered_map<int, int>array[int]
Handles negative numbers✅ Yes❌ No
Handles large values✅ Yes❌ No (impractical)
Memory efficiency for sparse data✅ Good (dynamic)❌ Poor (fixed, may waste space)
Access time⚡ O(1) average⚡ O(1)
Requires known value range❌ No✅ Yes
Supports non-integer keys (e.g. strings)✅ Yes❌ No
Memory usage for small dense range❌ Higher overhead✅ Very efficient
Works best whenValues are unknown/large/negativeValues are small & non-negative
Example input[-3, 5, 1000000000][1, 2, 2, 1]

Code:

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    // Function to find the majority element in an array
    int majorityElement(vector<int>& nums) {
        
        // Size of the given array
        int n = nums.size();
        
        // Hash map to store element counts
        unordered_map<int, int> mp;
        
        // Count occurrences of each element
        for (int num : nums) {
            mp[num]++;
        }
        
        /* Iterate through the map to
        find the majority element*/
        for (auto& pair : mp) {
            if (pair.second > n / 2) {
                return pair.first;
            }
        }
        
        // Return -1 if no majority element is found
        return -1;
    }
};

int main() {
    vector<int> arr = {2, 2, 1, 1, 1, 2, 2};
    
    // Create an instance of Solution class
    Solution sol;

    int ans = sol.majorityElement(arr);
    
    // Print the majority element found
    cout << "The majority element is: " << ans << endl;
    
    return 0;
}

Complexity Analysis:

  • Time Complexity:O(NxlogN) + O(N), where N is the size of the array.
    • This TC is for using a map data structure.
      • Insertion in the map takes log N time. And we are doing it for N elements. So, it results in the first term O(NxlogN).
      • The second O(N) is for checking which element occurs more than floor(N/2) times. On using unordered_map, the first term will be O(N) for the best and average case and for the worst case, it will be O(N^2).
  • Space Complexity:O(N) for using a map data structure.

3️⃣ Optimal Approach (Boyer-Moore Voting)

Intuition:

Imagine you are at a large party, and you want to determine which dish is the most popular. Each guest has brought a dish, and some dishes are brought by more guests than others. The party is large enough that one dish is guaranteed to be the majority dish, meaning it was brought by more than half of the guests.

Initial observation is as we move around the party, you decide to start keeping track of the dishes in a specific way. Begin with no specific dish in mind and no count. On seeing each dish, do the following:

  • If you don’t have a dish you’re tracking yet, start tracking the current dish and set its count to 1.
  • If the current dish matches the one you’re tracking, increase its count by 1.
  • If the current dish doesn’t match the one you’re tracking, decrease the count by 1. If the count drops to zero, stop tracking that dish and start tracking the next dish.

The idea is that at any point where the count of tracked dishes drops to zero, it means up to that point, the popularity of different dishes has balanced out. This reset allows you to focus on potentially more popular dishes as you continue through the party. At the end check which dish you ended up tracking last. This dish is your candidate for the most popular dish. To confirm if this dish is indeed the majority dish, recount its appearances to see if it indeed makes up more than half of all dishes at the party. If it does, then you have found your majority dish. If it doesn’t, there was an error in the process, but for this scenario, we assume the party is large enough to guarantee one majority dish.

Approach:

  1. Initialize 2 variables: count for tracking the count of elements and element for keeping a track of the element we are counting.
  2. Traverse through the given array. If count is 0 then store the current value of the array as element .
  3. If the current array value andelement are the same increase the count by 1. If they are different decrease the count by 1. The integer present in element should be the result expected.

Code:

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    // Function to find the majority element in an array
    int majorityElement(vector<int>& nums) {
        
        // Size of the given array
        int n = nums.size();
        
        // Count
        int cnt = 0;
        
        // Element
        int el; 
        
        // Applying the algorithm
        for (int i = 0; i < n; i++) {
            if (cnt == 0) {
                cnt = 1;
                el = nums[i];
            } else if (el == nums[i]) {
                cnt++;
            } else {
                cnt--;
            }
        }
        
        /* Checking if the stored element
         is the majority element*/
        int cnt1 = 0;
        for (int i = 0; i < n; i++) {
            if (nums[i] == el) {
                cnt1++;
            }
        }
        
        //return element if it is a majority element
        if (cnt1 > (n / 2)) {
            return el;
        }
        
        //return -1 if no such element found
        return -1;
    }
};

int main() {
    vector<int> arr = {2, 2, 1, 1, 1, 2, 2};
    
    // Create an instance of Solution class
    Solution sol;

    int ans = sol.majorityElement(arr);
    
    // Print the majority element found
    cout << "The majority element is: " << ans << endl;
    
    return 0;
}

Complexity Analysis:

  • Time Complexity:O(N) + O(N), where N is size of the given array.
    • The first O(N) is to calculate the count and find the expected majority element.
    • The second one is to check if the expected element is the majority one or not.
  • Space Complexity:O(1) no extra space used.
Your experience on this site will be improved by allowing cookies Cookie Policy