Problem

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

The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array. Problem Link

Example 1:

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

Example 2:

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

Constraints:

n == nums.length
1 <= n <= 5 * 104
-109 <= nums[i] <= 109

Brute force Approach

In this approach, we calculate the frequency of each element that we encounter

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

        for(int i=0;i<n; i++){
            int count = 1;
            for(int j=0; j<n; j++){
                if(i!=j && nums[i]==nums[j]) count+=1;
            }
            if(count>n/2) return nums[i];
        }
        return -1;
    }
}

The sole drawback is that we end up recalculating the frequencies of elements we've already come across. We can enhance this process by employing a sorting approach as well.

Time complexity: O(n^2)

Space complexity: O(1)

Dictionary or Map Approach

In this, we take advantage of the map where the map stores the frequency of all the elements. Here we iterate the frequency map and compare the values with n/2.

class Solution {
    public int majorityElement(int[] nums) {
        int n = nums.length;
        Map<Integer, Integer> freqMap = new HashMap<>();

        for(int key: nums){
            if(!freqMap.containsKey(key)){
                freqMap.put(key, 0);
            }
            int value = freqMap.get(key);
            freqMap.put(key, value+1);
        }

        for(int key: freqMap.keySet()){
            int value = freqMap.get(key);
            if(value>n/2) return key;
        }
        return -1;
    }
}

Time Complexity: O(n) (Assuming map gets key in O(1))

Space Complexity: O(n)

Moore's Voting Algorithm Visualization

Analogy with War

Let's consider a scenario resembling a war where several kings are engaged in battle with their respective armies. Each army is denoted by a unique number, and each soldier within an army is identified by the same number. In this conflict, soldiers can eliminate one soldier from an opposing army. Therefore, when two soldiers engage in combat, both are defeated as they can kill each other. Ultimately, at the end of the war, only one soldier or potentially no soldiers may remain if the war has been fully fought. The possibility exists that one or more soldiers could survive, but they will belong to the same army, unable to harm their fellow members.

In this type of warfare, victory goes to the army with the greatest number of soldiers.

Scenario 1

[2, 2, 2, 2, 2, 3, 3, 3, 3]

In this case, there are only two armies, numbered 2 and 3. Army 2 has a total of 5 members, while Army 3 has 4 members. Consequently, four members from each side will be eliminated, leaving one member of Army 2 alive, making Army 2 the victor.

Scenario 2

[2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4]

In this example, Army 2 has a total strength of 10, while Army 3 has a total strength of 4, and Army 4 also has a total strength of 4. Eight members of Army 2 will eliminate members of both Army 3 and Army 4, with the members of Army 2 also being eliminated in the process. In the end, only two members of Army 2 will remain alive, making Army 2 the winner.

This solution is easily implementable by maintaining a count variable for the number of soldiers from Army 2. The count is increased when a member of Army 2 is encountered and decreased when a member of another army is encountered. This approach is applicable when the array is sorted.

Scenario 3: Randomize the Array

[3, 3, 2, 2, 2, 2, 3, 4, 2, 4, 3, 4, 4, 2, 2, 2, 2, 2]

In this case, we iterate through the elements one by one. We still use a single count variable for tracking. We initially assume that the first encountered army member is the winner, and we increase or decrease the count accordingly. When the count reaches 0, it signifies that all members within that particular group have been eliminated up to that point in the iteration. This can be observed between index 0 and 3, where everyone in this group is defeated. We then move to the next index, assuming that this is the winning army, and adjust the count accordingly. When we iterate from index 4 to 7, the count becomes 0, indicating that the entire group is defeated. Afterward, a smaller group of [2, 4] remains, where members of both Army 2 and Army 4 eliminate each other. By continuing this process, only members of Army 2 will ultimately remain alive, declaring Army 2 as the winner.

Verification at the End of the War

It's essential to verify the winner through the described logic, as there's a possibility that a minority army could be incorrectly declared as the winner. For instance:

[2, 2, 2, 2, 3, 3, 3, 3, 4]

In this example, members of Army 2 and Army 3 eliminate each other, but a member of Army 4 survives. Following our algorithm, we might mistakenly declare Army 4 as the winner. To ensure complete accuracy, we iterate through the array and count the occurrences of each element. If any element's count is less than n/2, we declare there is no winner, signifying the absence of a majority army.

Moore's Java Code

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

        for(int member: nums){
            if(army==member) count+=1;
            else if(count!=0) count-=1;
            else{
                army = member;
                count = 1
            }
        }

        //verification
        int actualCount = 0;
        for(int member:nums){
            if(army==member) actualCount+=1;
        }

        if(actualCount<n/2) return -1;

        return army;
    }
}

Time Complexity: O(n)

Space Complexity: O(1)

We can skip the verification part for the given problem because it is mentioned that the majority element always exists in the array

169. Majority Element - Moore's Voting Algorithm

Table of contents