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
2
3
4
5
Input: [3,2,3]
Output: 3

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

Follow up: Jesus. Many possible solutions.

Analysis

Brute-Force

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int majorityElement(int[] nums) {
  int n = nums.length;
  for (int curr : nums) {
    int count = 0;
    for (int val : nums) {
      if (curr == val) {
        count += 1;
      }
    }
    if (count > n / 2) {
      return curr;
    }
  }
  return -1;
}

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

HashMap

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

1
2
3
4
5
6
7
8
9
10
11
12
13
// Use Hash Map
public int majorityElement(int[] nums) {
  Map<Integer, Integer> map = new HashMap<>();
  for (int val : nums) {
    int count = map.getOrDefault(val, 0);
    map.put(val, count + 1);
    // check
    if (count > nums.length / 2) {
      return val;
    }
  }
  return -1;
}

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.

Source: LeetCode

1
2
3
4
5
6
7
8
9
10
11
// sort first
public int majorityElement(int[] nums) {
  // Length / 2  =>  right-leaning mid
  // even:  0  1  2  3
  //              ^        mid = 4 / 2 = 2
  //  odd:  0  1  2  3  4
  //              ^        mid = 5 / 2 = 2
  Arrays.sort(nums);
  return nums[nums.length / 2];
  // actually you need to confirm the result
}

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// randomization
public int majorityElement(int[] nums) {
  int n = nums.length;
  Random rand = new Random();
  while (true) {
    // pick a candidate
    int idx = rand.nextInt(n);
    int candidate = nums[idx];
    // check the count
    int count = 0;
    for (int i = 0; i < n; ++i) {
      if (nums[i] == candidate) count += 1;
    }
    // check if it is a majority element
    if (count > n / 2) {
      return candidate;
    }
  }
  // throw new IllegalArgumentException();
  // return -1;
}

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public int majorityElement(int[] nums) {
  int n = nums.length;
  return majorityElement(nums, 0, n - 1);
}

private int majorityElement(int[] nums, int lo, int hi) {
  if (lo == hi) {
    return nums[lo];
  }
  int mid = lo + (hi - lo) / 2; // left-leaning
  int left = majorityElement(nums, lo, mid);
  int right = majorityElement(nums, mid + 1, hi);

  if (left == right) { // agree on
    return left;
  }

  // disagree on
  int leftCount = countInRange(nums, left, lo, hi); // O(N)
  int rightCount = countInRange(nums, right, lo, hi); // O(N)

  return (leftCount > rightCount) ? left : right;
}

private int countInRange(int[] nums, int val, int lo, int hi) {
  int count = 0;
  for (int i = 0; i <= hi; ++i) {
    if (nums[i] == val) {
      count += 1;
    }
  }
  return count;
}

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
2
[7, 7, 5, 7, 5, 1 | 5, 7 | 5, 5, 7, 7 | 7, 7, 7, 7]
 1  2  1  2  1  0   1  0  -1 -2 -1  0   1  2  3  4

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

1
2
[7, 7, 5, 7, 5, 1 | 5, 7 | 5, 5, 7, 7 | 5, 5, 5, 5]
 1  2  1  2  1  0   1  0   1  2  1  0   1  2  3  4

Note: Check if count == 0 before updating it.

1
2
3
4
5
6
7
8
9
10
11
12
public int majorityElement(int[] nums) {
  int count = 0;
  Integer candidate = null;
  for (int val : nums) {
    if (count = 0) {
      candidate = val;
    }
    count += (val == candidate) ? +1 : -1;
  }
  // possible verification
  return count;
}

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