A good design of an algorithm is never making the problem more complicated, instead, you will find it so simple that normally takes a few lines of code yet maintains the time and space complexity minimal.

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 exists in the array.

LeetCode 169

Analyze

Brute Force

A quick and naive thought to solve this problem is using Brute Force approach. Basically, using two for-loops, count the number of appearance for each element. Once the counter exceeds the ⌊n/2⌋, then we return the element.

Seems pretty straightforward, but what about n = 1 million? Obviously, this approach is not time-efficient. The time complexity will be O(n^2).

HashMap

This seems to be more time efficient, as the lookup time for HashMap is constant(At least most of the time). So the idea would be: while we iterate the array, we save the element as the key in the HashMap, the counter for the element as the value.

Once we complete the iteration on the array, we will have the HashMap containing the unique elements and their appearance counters.

1
2
3
4
5
6
7
8
def majorityElement(self, nums: List[int]) -> int:
    d = {}
    for n in nums:
        d[n] = d[n]+1 if n in d else 1

    for k in d.keys():
        if d[k] > len(nums)/2:
            return k

This approach takes two separate iterations, so the time complexity will be O(n+n), which can be simplified as O(n). How about space complexity? Since we are using an additional HashMap, the space complexity will be O(n) as well.

Can we solve it in constant space complexity?

Boyer-Moore Majority Voting Algorithm

A little bit background of this algorithm from Wikipedia:

The Boyer–Moore majority vote algorithm is an algorithm for finding the majority of a sequence of elements using linear time and constant space. It is named after Robert S. Boyer and J Strother Moore, who published it in 1981, and is a prototypical example of a streaming algorithm.

As you can see, the algorithm only uses linear time and constant space.

Idea

The idea is that we use two additional variables:

  • candidate: to keep track of the potential candidate at each step.
  • counter: the number of appearance of the candidate at that step.

Initially, the current candidate is None and the counter is 0. As we iterate the array over an element e, we will do the following check:

  • If the counter is 0, we set the current element e as the new candidate.
  • If the counter is not 0, we will check:
    • If the current element e is the same as the candidate, we increment the counter by 1
    • Else we decrement the counter by 1

Example

Let’s take this array as an example: [2,2,1,1,3,2,2].

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
                  CAND    COUN
  2 2 1 1 3 2 2   None     0
^

                  CAND    COUN
  2 2 1 1 3 2 2    2       1
  ^

                  CAND    COUN
  2 2 1 1 3 2 2    2       2
    ^

                  CAND    COUN
  2 2 1 1 3 2 2    2       1
      ^

                  CAND    COUN
  2 2 1 1 3 2 2    2       0
        ^

                  CAND    COUN
  2 2 1 1 3 2 2    3       1
          ^

                  CAND    COUN
  2 2 1 1 3 2 2    3       0
            ^

                  CAND    COUN
  2 2 1 1 3 2 2    2       1
              ^

After the iteration, the candidate is 2, which is the majority element of this array.

You can validate with any other scenario following the same approach.

Implementation

1
2
3
4
5
6
7
8
def majorityElement(self, nums: List[int]) -> int:
    candidate = None
    counter = 0
    for n in nums:
        if counter == 0:
            candidate = n
        counter += 1 if n == candidate else -1
    return candidate

Obviously, there is only one iteration and allocates only constant additional memory. Therefore, the time complexity would be O(n), and space complexity would be O(1).

If you are interested in the mathematical proof of this approach. One of the inventor Moore attaches their publication here.

The beauty and power of algorithms.