Reference: LeetCode

Difficulty: Easy

Here is a nice article about Majority Voting Algorithm by Greg Grothaus.

## Problem

Given an array of size $n$, find the majority element. The majority element is the element that appears

more than`⌊n/2⌋`

times.

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

**Example:**

1 | Input: [3,2,3] |

**Follow up:** Jesus. Many possible solutions.

## Analysis

### Brute-Force

1 | public int majorityElement(int[] nums) { |

**Time:** $O(N^2)$**Space:** $O(1)$

### HashMap

It reduces the runtime to $O(N)$ with some extra space $O(N)$.

1 | // Use Hash Map |

**Time:** $O(N)$**Space:** $O(N)$

### Sorting

If the elements are sorted, the majority element is guaranteed to be at right-leaning or left-leaning `mid`

. Think of two extreme cases when the majority element starts at the beginning or reaches the tail.

1 | // sort first |

**Time:** $O(N\log{N})$**Space:** $O(1)$ (in-place) or $O(N)$ (non-destructive)

### Randomization

Because more than `⌊n/2⌋`

array indices are occupied by the majority element, a random array index is likely to contain the majority element.

**Note:** The commented lines are not allowed (`unreachable statement`

), since the compiler knows that the condition of the loop is `true`

.

1 | // randomization |

**Time:** $O(\infty)$**Space:** $O(1)$

It is theoretically possible for this algorithm to r un indefinitely, so the worst possible runtime is unbounded. But in fact the expected runtime is far better which is $O(N)$.

### Divide and Conquer

**Idea:** If we know the majority element in the left and right halves of an array, we can determine which is the global majority element in $O(N)$.

- The base case of this problem is when the slice is length-1, and the majority element for this slice is just the only element.
- If the current slice is longer than length-1, we must combine the results from the left slice and right slice.
- If they agree on the majority element, then this element is the global majority element.
- If they disagree, we need to count the occurrences of the left and right majority elements to get the answer since we know that only one of them can be right.

1 | public int majorityElement(int[] nums) { |

**Time:** $T(N) = 2T(N/2) + 2N = O(N\log{N})$**Space:** $O(\log{N})$

### Boyer-Moore Voting Algorithm

The idea is to count instances of the majority element as $+1$ and instances of any other element as $-1$, and then summing them would make the majority element obvious.

- We have a
`count`

variable initialized with $0$. We**increment it by one**whenever we see an instance of the candidate, and**decrement it by one**whenever we see something else. - When
`count`

equals $0$, we effectively forget about everything before the current index. Also, we consider the element at the next index as a new candidate of the majority element. - Eventually, a suffix will be found for which
`count`

does not hit`0`

.

**Note:** It is still possible that there is no majority element at all (e.g. `1 4 1 1 3 5 9 8 7`

, fake candidate is `7`

). So actually we need a second pass to confirm the result.

Example 1: (n = 16, #7 = 10, #5 = 5, #1 = 1)

1 | [7, 7, 5, 7, 5, 1 | 5, 7 | 5, 5, 7, 7 | 7, 7, 7, 7] |

Example 2: (n = 16, #7 = 6, #5 = 9, #1 = 1)

1 | [7, 7, 5, 7, 5, 1 | 5, 7 | 5, 5, 7, 7 | 5, 5, 5, 5] |

**Note:** Check if `count == 0`

before updating it.

1 | public int majorityElement(int[] nums) { |

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