# Go4Fun - Functional programming and more # Rust Interview Puzzles: Find the majority element in a vector

### Problem

In a provided vector `vec` we need to find the majority element, if it is present. The majority element is the element that appears in the vector more than `n / 2` times, where `n` is a size of the vector `vec`.

#### Example 1:

Input: `vec = [4, 8, 7, 4, 4, 5, 4, 3, 1, 4, 4]`
Output: `4`
Explanation: The majority element is `4` because it appears in the vector `6` times (more than `n / 2 = 11 / 2 = 5`).

#### Example 2:

Input: `vec = [4, 8, 7, 4, 4, 5, 4, 3, 1, 4]`
Output: `None`
Explanation: There is no the majority element in the vector. Even though `4` is the most common element, it is not the majority element, because it appears only `5` times (not more than `n / 2 = 10 / 2 = 5` times).

#### Example 3:

Input: `vec = `
Output: `1`

#### Example 4:

Input: `vec = [1, 2]`
Output: `None`

### Solution

``````fn find_majority_element(vec: &Vec<i32>) -> Option<i32> {
let mut m = 0;
let mut i = 0;
//first pass:
vec.iter().for_each(|&x| {
if i == 0 {
m = x;
i = 1;
} else if m == x {
i = i + 1;
} else {
i = i - 1;
}
});
//second pass:
let count = vec
.iter()
.fold(0, |count, &x| if x == m { count + 1 } else { count });
//return Some(m) if actual majority, None otherwise:
(count > vec.len() / 2).then(|| m)
}
``````

### Explanation

The solution for this problem uses Boyer–Moore majority vote algorithm:

``````Initialize an element m and a counter i with i = 0
For each element x of the input sequence:
If i = 0, then assign m = x and i = 1
else if m = x, then assign i = i + 1
else assign i = i − 1
Return m
``````

Also we need the second pass over the vector `vec` because, even when there is no the majority element, the algorithm would yield one of the elements as the result (`m`). On the second pass, we calculate a number of times (`count`) we encounter `m` element to check if that is the actual majority (it appears more than `vec.len() / 2` times). If that is the case - we found the majority element. If not - we return `None`.

### Complexity

The time complexity of this solution is `O(n)` (`n` is a size of the input vector), but we need to iterate over the input vector twice. The auxiliary space complexity is constant (`O(1)`).

Rust Playground with this code