Majority Element

Problem Description

You are given an array of numbers, and your job is to find the majority element. The majority element is the one that shows up more than half the time in the array.

Example 1:

Input: nums = [3, 2, 3]
Output: 3
Explanation:
In this array, the number 3 appears twice, and the number 2 appears once. Since 3 appears more than half the time (which is 2 out of 3 elements), it is the majority element.

Example 2:

Input: nums = [2, 2, 1, 1, 1, 2, 2]
Output: 2
Explanation:
In this array, 2 appears four times, and 1 appears three times. Since 2 appears more than half the time (which is 4 out of 7 elements), it is the majority element.

Constraints:

n == nums.length
1 <= n <= 5 * 10⁴
-10⁹ <= nums[i] <= 10⁹

Brute Force Approach:

Now, the first thing that comes to mind is to check all the elements in the array. We can count how many times each element appears, and the one that appears more than half the time (n/2) will be the majority element.

How do we do this?

1. We’ll go through the array one element at a time.
2. For each element, we’ll count how often it shows up in the entire array.
3. If we find an element that appears more than half the time, we return that as the majority element.

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int n = nums.size();

        // Iterate through each element in the array
        for (int i = 0; i < n; i++) {

            // Initialize count for the current element
            int count = 0;

            // Count occurrences of the current element
            for (int j = 0; j < n; j++) {
                if (nums[j] == nums[i]) {
                    count++;
                }
            }

            // Check if the count is greater than n/2
            if (count > n / 2) {

                // Return the majority element
                return nums[i];
            }
        }

        // This line is not needed as the majority element is guaranteed to
        // exist
        return -1;
    }
};

class Solution {
    public static int majorityElement(int[] nums) {
        int n = nums.length;

        // Iterate through each element in the array
        for (int i = 0; i < n; i++) {

            // Initialize count for the current element
            int count = 0;

            // Count occurrences of the current element
            for (int j = 0; j < n; j++) {
                if (nums[j] == nums[i]) {
                    count++;
                }
            }

            // Check if the count is greater than n/2
            if (count > n / 2) {
       
                 // Return the majority element
                return nums[i];
            }
        }
        
        // This line is not needed as the majority element is guaranteed to exist
        return -1; 
    }
}

class Solution(object):
    def majorityElement(self, nums):
        n = len(nums)
        # Iterate through each element in the array

        for i in range(n):

            # Initialize count for the current element
            count = 0

            # Count occurrences of the current element
            for j in range(n):
                if nums[j] == nums[i]:
                    count += 1

            # Check if the count is greater than n/2
            if count > n // 2:

                # Return the majority element
                return nums[i]

        # This line is not needed as the majority element is guaranteed to exist
        return -1  

var majorityElement = function(nums) {
    const n = nums.length;
    // Iterate through each element in the array

    for (let i = 0; i < n; i++) {

        // Initialize count for the current element
        let count = 0;         
        
        // Count occurrences of the current element
        for (let j = 0; j < n; j++) {
            if (nums[j] === nums[i]) {
                count++;
            }
        }

        // Check if the count is greater than n/2
        if (count > Math.floor(n / 2)) {

            // Return the majority element
            return nums[i]; 
        }
    }

    // This line is not needed as the majority element is guaranteed to exist
    return -1;
};

Can we optimize it?

In the brute force approach, we're calculating the frequency of each element multiple times, which makes it slower. Instead, how about we calculate the frequency of each element just once? 

What if we could count the occurrences of all the elements, indicating how many times they are present? This would eliminate the need for the second loop to traverse the array entirely. 

We need a data structure that allows us to know the frequency of elements in constant time, so we can instantly determine how many times an element is present without having to go through the entire list. This significantly improves the efficiency of the process.

Which data structure can be found useful here?

Yes, you’re right! We could use something like a hash table to store the count of each element as we go through the array.

But wait—our elements range from -10⁹ to 10⁹, meaning the numbers can be both negative and spread across a huge range. Building a hash table with such a large range would lead to inefficient memory usage, as we'd need an enormous table to account for all possible values.

So, how do we tackle this? 

The answer is hash maps. Unlike arrays or hash tables with fixed sizes, a hash map dynamically stores only the elements we encounter, along with their counts. This way, we avoid wasting memory on values that don't exist in the array, making the solution both space-efficient and faster.

Once we've built this frequency map, we can simply check which element appears more than n/2 times, and return that as the majority element. 

This way, we're reducing the extra work and bringing the time complexity down to O(n), which is much faster and will work more efficiently with larger inputs.

Doesn’t that sound like a great step forward? Let’s go for it!

class Solution {
public:
    int majorityElement(vector<int>& nums) {

        // Create a hash map to store counts
        unordered_map<int, int> countMap;
        for (int num : nums) {

            // Increment the count for the current number
            countMap[num]++;
        }

        // Find the majority element
        for (auto& entry : countMap) {
            if (entry.second > nums.size() / 2) {

                // Return the element if its count is greater than n/2
                return entry.first;
            }
        }

        // This line won't be reached as per the problem's guarantee
        return -1;
    }
};

class Solution {
    public int majorityElement(int[] nums) {

        // Create a hash map to store counts
        HashMap<Integer, Integer> countMap = new HashMap<>();         
        for (int num : nums) {

            // Increment the count for the current number
            countMap.put(num, countMap.getOrDefault(num, 0) + 1);         
         }

        // Find the majority element
        for (int key : countMap.keySet()) {
            if (countMap.get(key) > nums.length / 2) {

                // Return the element if its count is greater than n/2
                return key;
            }
        }

        // This line won't be reached as per the problem's guarantee
        return -1;
    }
}

class Solution(object):
    def majorityElement(self, nums):
        
        # Create a hash map to store counts
        countMap = {} 
        for num in nums:

            # Increment the count for the current number
            countMap[num] = countMap.get(num, 0) + 1  

        # Find the majority element
        for key, count in countMap.items():
            if count > len(nums) // 2:

                # Return the element if its count is greater than n/2
                return key    

        # This line won't be reached as per the problem's guarantee
        return -1 
            

var majorityElement = function(nums) {
    
    // Create a hash map to store counts
    const countMap = {};
    for (const num of nums) {

        // Increment the count for the current number
        countMap[num] = (countMap[num] || 0) + 1;     
    }

    // Find the majority element
    for (const key in countMap) {
        if (countMap[key] > nums.length / 2) {

            // Return the element if its count is greater than n/2
            return parseInt(key);         
         }
    }

    // This line won't be reached as per the problem's guarantee
    return -1;
};

Can there be a better approach? 

Yes, there’s definitely a smarter way to solve this problem—one that works in linear time and uses constant space. 

Want to know how?

Imagine a big multiplayer game, where several teams are playing together. Each team has a bunch of players, and the goal is to eliminate the players from other teams. 

Here’s the twist: when two players from different teams collide or fight, both of them get eliminated. So, every time players from two teams meet, they both lose one player. Now, let's say one team has more than half the total players—that team is the majority.

Here’s how it plays out:

When a player from the majority team faces off with a player from a smaller team, both are eliminated, but the majority team will still have more players left.

The majority team keeps losing players in these fights, but it can always afford to because it started with more players than anyone else.

Even if the majority team goes through multiple battles, it will always have some players left because no other team can match its numbers. At the end of the game, all the smaller teams will be eliminated, and only the majority team will survive.

For example, let’s say there are 100 players in total, and the majority team has 51 players (since 51 is more than half of 100). All the other teams together have 49 players. Let’s walk through this step by step:

The first time a player from the majority team (51 players) collides with a player from the smaller teams (49 players), both are eliminated. Now, the majority team has 50 players, and the smaller teams combined have 48 players.

This process keeps repeating—each time a player from the majority team collides with a player from the other teams, both are eliminated. After several battles, the numbers continue to decrease:

Majority team: 50 → 49 → 48 → 47…Other teams: 48 → 47 → 46 → 45...

After 49 collisions, all players from the smaller teams are eliminated. The majority team still has 2 players left, while the smaller teams have none.

Even after all these collisions, the majority team survives with 2 players.

Now suppose we have three teams, Team A with 51 players, Team B with 25 players, and Team C with 25 players. Let's assume that Teams B and C clash with each other first. In their battle, all players from both teams get eliminated, resulting in both Team B and Team C being knocked out of the game. As a result, Team A, with all 51 of its players still intact, wins the game without losing any players. This would be the best-case scenario for Team A, as it secures victory while preserving the maximum number of its players.

No matter how many fights they go through, the majority team will always have players left because they started with more than half the total number of players.

In the same way, think about an array of numbers. If there's an element that appears more than half the time, it acts just like the majority team in the game. As we go through the array:

Whenever we encounter the majority element, it "survives" and stays in the lead.

If we encounter a different element, it's like a battle where one player from the majority element "fights" with the new element, and they both get eliminated, reducing the count of the majority element.

But since the majority element appears more than half the time, it will always stay ahead in the game of eliminations, just like the team with the most players.

In the end, even after all the encounters with other elements, the majority element will be the one left standing—just like the majority team wins in the game!

So, just like the strongest team with more than half the players wins in the game, the majority element in an array is the one that will always "survive" and be left at the end of our process.

Using this idea, we can efficiently find the majority element in an array. Simple and effective!

Let it Visualise it with the visuals

How Can We Do That?

The main idea is simple: if there's a majority element in an array, it will always "win" over the other elements, even if we encounter different ones.

Here’s how it works:

Imagine we have an array where most of the elements are 1, and the rest are -1. If we sum this array, the result will always be positive, right? That's because each 1 cancels out a -1, and since 1 is the majority, it remains in the end.

Similarly, when we compare the majority element with other elements, the majority will always "survive" because it's more frequent.

Now, let’s break it down:

• Let’s say we have a majority element in the array, which we'll call the candidate.
• As we move through the array, we increase the count if we see the same candidate, and decrease it if we encounter a different element.

The count for the candidate will always stay positive because it appears more than any other element (since it's the majority).

But wait, how do we know what the majority element is in the first place?

Here’s the clever part: we start with no candidate and a count of zero.  As we go through the array, we can take the first element as our candidate and start by increasing the count. Then, as we continue:

• If an element matches the current candidate, we increase the count.
• If it doesn’t match, we decrease the count.
• When the count drops to zero, we pick the current element as the new candidate and reset the count.

By the time we finish going through the array, the candidate we’re left with will be the majority element, because count will always stay positive for the majority element.

Simple, right?

This approach is also called Moore’s Voting algorithm.

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        
        // Initialize count to 0
        int count = 0;        

        // Initialize candidate to 0
        int candidate = 0;   
        
        // Iterate through each number in the array
        for (int num : nums) {
            if (count == 0) {

                // When count is 0, set current number as the new candidate
                candidate = num;
            }
            
            // Increase count if current number matches candidate
            if (num == candidate) {
                count++;
            } else {

                // Otherwise, decrease the count
                count--;
            }
        }
        
        // Return the candidate which is the majority element
        return candidate;
    }
};

class Solution {
    public int majorityElement(int[] nums) {
        
        // Initialize count to 0
        int count = 0;   
  
        // Initialize candidate to 0  
        int candidate = 0;   
        
        // Iterate through each number in the array
        for (int num : nums) {
            if (count == 0) {

                // When count is 0, set the current number as the new candidate
                candidate = num;
            }
            
            // Increase count if current number matches candidate
            if (num == candidate) {
                count++;
            } else {

                // Otherwise, decrease the count
                count--;
            }
        }
        
        // Return the candidate which is the majority element
        return candidate;
    }
}

class Solution(object):
    def majorityElement(self, nums):
        
        # Initialize count to 0
        count = 0 

        # Initialize candidate to 0
        candidate = 0 
        
        # Iterate through each number in the array
        for num in nums:
            if count == 0:

                # When count is 0, set the current number as the new candidate
                candidate = num
            
            # Increase count if the current number matches the candidate
            if num == candidate:
                count += 1
            else:

                # Otherwise, decrease the count
                count -= 1
        
        # Return the candidate which is the majority element
        return candidate
        

var majorityElement = function (nums) {
    
    // Initialize count to 0
    let count = 0;

    // Initialize candidate to 0 
    let candidate = 0;

    // Iterate through each number in the array
    for (let num of nums) {
        if (count === 0) {

            // When count is 0, set the current number as the new candidate
            candidate = num;
        }

        // Increase count if the current number matches the candidate
        if (num === candidate) {
            count++;
        } else {

            // Otherwise, decrease the count
            count--;
        }
    }

    // Return the candidate which is the majority element
    return candidate;
};

Learning Tip

Now we have successfully tackled this problem, let's try these similar problems.