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

#java #algorithms #beginners #programming

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;
    }

(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];
    }

(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;
    }

(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;

    }