169. Majority Element / Moore

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

Intuition

Moore voting algorithm

2 2 1 1 | 2 2 1 1 |  3
Basically check windows all windows will get calncelled
Max is returned

Links

https://leetcode.com/problems/majority-element/

Video Links

https://www.youtube.com/watch?v=AoX3BPWNnoE&list=PLgUwDviBIf0rPG3Ictpu74YWBQ1CaBkm2&index=17

Approach 1:

Moore voting algorithm

C++

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

        for(int i=0;i<nums.size();i++){
            if(count==0)
                el=nums[i];

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

        return el;
        

    }
};

Approach 2:

C++

Approach 3:

C++

Approach 4:

C++