# 169. Majority Element

Given an array find the element that appears more than $$\frac{n}{2}$$ times ( assume such majority element always exists in the array )

{% hint style="info" %}
Solve this problem in linear time $$\text{O}(n)$$ using constant space
{% endhint %}

## Intuition

* We can use the simple voting mechanism where anything different is considered a vote against.
  * Only the majority element will have vote in his favour.

## Approach

* Track the `candidate` & the number of `vote` i.e its occurrence.
  * If we encounter an element different from the `candidate` decrease the `vote` count
  * If for the current `candidate` the `votes` become `0` replace it
* At the end only the max occurring element will remain.

## Complexity

| Space Complexity | Time Complexity |
| ---------------- | --------------- |
| $$\text{O}(n)$$  | $$\text{O}(1)$$ |

* No extra space is needed

## Code

```java
class Solution {
    public int majorityElement(int[] nums) {
    
        // we count the votes 
	// number of votes will be > 0 only for the majority element
        int count = 1, candidate = nums[0];
        
        for (int i = 1; i < nums.length; ++i) {
            if(nums[i] == candidate) {
                count++;
            } else {
            	// if the element is different consider it as vote againts 
                count--;
                // if votes is 0 then replace the candiate
                if(count == 0) {
                    candidate = nums[i];
                    count = 1;
                }
                
            }
        }

        

        return candidate;
    }
}
```