DEV Community

Cover image for LeetCode: Majority Element (Boyer-Moore Majority Voting Algorithm)
Tisha Agarwal
Tisha Agarwal

Posted on

7 2

LeetCode: Majority Element (Boyer-Moore Majority Voting Algorithm)

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.

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

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

This is a EASY LEVEL question but it is very important.
It can easily be solved using two or three technics. But the main algorithm that we'll learn while solving it is Boyer-Moore Majority Voting Algorithm

To solve the question click here:(https://leetcode.com/problems/majority-element/)

The Boyer-Moore voting algorithm is one of the popular optimal algorithms which is used to find the majority element among the given elements that have more than N/ 2 occurrences. This works perfectly fine for finding the majority element which takes 2 traversals over the given elements, which works in O(N) time complexity and O(1) space complexity.

Approaches-
(1) Nested for-loop :
Time Complexity: O(N^2)
Space Complexity: O(1)

JAVA CODE:

public static int majorityElement(int[] nums) {

        int n=nums.length;
        int max=0,ele=nums[0];
        for(int i=0;i<nums.length;i++)
        {
            int count=0;
            for(int j=i;j<nums.length;j++)
            {
                if(nums[i]==nums[j])
                    count++;
            }
            if(count>max)
            {
                max=count;
                ele=nums[i];
            }
        }
        if(max>=(int)(n/2))
            return ele;

        return -1;
    }
Enter fullscreen mode Exit fullscreen mode

(2) Sorting:
Time Complexity: O(NlogN)
Space Complexity: O(1)

JAVA CODE:

public static int majorityElement_m2(int nums[])
    {
            Arrays.sort(nums);
            return nums[nums.length/2];
    }
Enter fullscreen mode Exit fullscreen mode

(3) HashMap:
Time Complexity: O(N)
Space Complexity: O(N)

JAVA CODE

public static int majorityElement_m3(int[] nums) {

        HashMap<Integer,Integer> hm=new HashMap<>();

        for(int i=0;i<nums.length;i++)
        {
            if(hm.containsKey(nums[i]))
                hm.put(nums[i] , hm.get(nums[i])+1);
            else
                hm.put(nums[i],1);
        }
        int answer =0;
     for (Map.Entry<Integer, Integer> entry : hm.entrySet())
     {
         if(entry.getValue()>nums.length/2)
         {
             answer = entry.getKey();
         }
     }
    return answer;
    }
Enter fullscreen mode Exit fullscreen mode

(4)Boyer-Moore Majority Voting Algorithm:
Time Complexity: O(N)
Space Complexity: O(1)

JAVA CODE

public static int majorityElement_m4(int[] nums) {
        int ans=nums[0];
        int count=1;
        for(int i=1;i<nums.length;i++)
        {
                if(nums[i]==ans)
                    count++;
                else
                    count--;

        if(count==0)
        {
             ans=nums[i];
            count=1; 
        }

        }
        return ans;

    }
Enter fullscreen mode Exit fullscreen mode

Sentry image

See why 4M developers consider Sentry, “not bad.”

Fixing code doesn’t have to be the worst part of your day. Learn how Sentry can help.

Learn more

Top comments (1)

Collapse
 
isurumax26 profile image
Isurumax26

I think sorting approach is incorrect.

Example :
Input: nums = [1, 1, 2, 3]
Output: 2 but should be 1