Striver's SDE Sheet Journey - #15 Majority Element (>N/2 times)

Problem Statement :-
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

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

Result : 2

Solution 1

using sorting,we can easily find the majority element in an array.
lets understand this approach step by step.

step-1 sort the array nums.

stpe-2 initialize three variables max = 0, count = 1, majEle = 0 .

step-3 run a loop from i=1 to n-1.

1. increase counting if the adjacent elements are the same..
if nums[i] == nums[i+1] then count++

2. if not nums[i] == nums[i+1], start recounting for new majority element.

3. if count > max then re-assign new max & majEle

Java

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

        if(nums.length == 1) return nums[0];
        Arrays.sort(nums);

        int max =0;
        int majEle = 0;

        int count = 1;

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

            }else{
                count = 1;
            }

             if(count > max) {
                    max = count ;
                    majEle = nums[i];
                }
        }

        return majEle;

    }
}

Time Complexity : O(nlogn) + O(n)
Space Complexity : O(1)

Solution 2

by using Boyer–Moore majority vote algorithm, we can solve this problem in O(n) time complexity

in this algorithm, we increase or decrease the count of the majority element, in the last, we will get our majority element.

step-1 initialise two variables majEle = nums[0], count = 1

step-2 run a loop from i=1 to n, then

1. if we found the majEle, increase the count by 1
2. if not majEle, decrease the count by 1
3. if count become 0 then, re-initialse majEle & count

Java

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

        int majEle = nums[0];
        int count = 1;

        for(int i=1; i<nums.length; i++){

            if(count == 0){
                majEle = nums[i];
                count++;

            }else if(nums[i] == majEle){
                count++;
            }else{
                count--;
            }
        }

        return majEle;

    }
}

Thank you for reading this article. save it for future use.
if you found something, let me in the comment section.