# Majority Element

The `majority element`

is the element that appears more than `⌊size/2⌋`

times.

Let's see several examples.

If the input array is `[1, 1, 3]`

, the majority item is `1`

because it occurs `2`

times and it's more than `3/2`

(where `3`

- array size). so `1`

- the majority element.

If the input array is `[1, 1, 3, 3, 4, 3]`

, the majority element is 3 because it occurs `3`

times and it equals `6/2`

(where 6 - array size). So `3`

- the majority element. All other elements occur less than `6/2`

.

## Algorithm

There are several ways how to find a majority element in an array.

### Using a dictionary or HashMap

The goal is to store each element's frequency in the dictionary and return the element if its frequency becomes more than `array size/2`

. The time complexity of this algorithm is `O(n)`

. The algorithm requires `O(n)`

space to store elements. It's a working algorithm, but it could be done `better`

.

### Boyer–Moore Majority Vote Algorithm

Using this algorithm, we can find a `majority element`

in `linear time`

and `constant space`

. The main idea is to count the majority element occurrence while traversing an array.

- In the beginning, the algorithm sets the first array element a majority element
- During traversing an array, we count the
`majority`

element occurrence.- If we see the
`same`

element as the majority element, we`increment`

the count. - If we see a
`different`

element, we`decrement`

the count.- if the count is less than zero, we set a current element as a new
`majority`

element.

- if the count is less than zero, we set a current element as a new

- If we see the

## Code

```
public int MajorityItem(int[] array)
{
if (array == null || array.Length == 0)
{
return -1;
}
if (array.Length == 1)
{
return array[0];
}
int count = 1;
int result = array[0];
for (int i = 1; i < array.Length; i++)
{
if (array[i] == result)
{
count++;
}
else
{
count--;
if (count == 0)
{
result = array[i];
count = 1;
}
}
}
return result;
}
```

**Time Complexity:** `O(n)`