> For the complete documentation index, see [llms.txt](https://joshualbarb.gitbook.io/leetcode-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://joshualbarb.gitbook.io/leetcode-problems/repeat-missing-numbers/majority-element.md).

# Majority Element

## Problem

Given an array of size n, find the majority element. The majority element is the element that appears **more than** `⌊ n/2 ⌋` times.

You may assume that the array is non-empty and the majority element always exist in the array.

{% hint style="info" %}
Example:

```
Input: [3,2,3]
Output: 3
```

```
Input: [2,2,1,1,1,2,2]
Output: 2
```

{% endhint %}

### Thought Process

![](/files/-MMwPp-UeLMorWGCunJu)

* **Moore's Voting Algorithm**: Moore's Voting Algorithm is an algorithm for finding the majority in a sequence of elements using linear time and constant space.

* For this problem, we will:
  * 1\) Find the candidate with $$count > 0$$ (this is where we use Moore's to find a potential candidate for majority element) 

    * **However,** just because its the candidate does not mean it occurs more than $$n/2$$ times. This is why we have to verify it

  * 2\) Iterate back through the array to verify this candidate appears more than $$n/2$$ times.

## Solution

```
class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        verify = len(nums)//2
        major = nums[0]
        count = 1
        
        for i in range(1,len(nums)):
            if nums[i] == major:
                count+=1
            elif(nums[i]!=major):
                count-=1
            if count == 0:
                count = 1
                major = nums[i]
        count2 = 0
        for i in range(len(nums)):
            if nums[i] == major:
                count2+=1
        if count2 > verify:
            return major
```

## Key Facts

![](/files/-MMwRvTjVBk68IPKcA8P)

* Moore's Voting Algorithm is important for this problem as it helps us potentially find the majority element. We then have to verify if this element is in fact the majority element

* We intially have to set the first element as the majority element to start.

## Time Complexity

* **Time:** $$O(n)$$ 
* **Space:** $$O(1)$$