DAA Blog Assignment: Boyer-Moore majority voting algorithm

This algorithm is a pretty simple algorithm to return the majority element of an array in a *single pass*. The logic is so simple it’s quite mindblowing honestly 🤯🤯🤯🤯🤯

written by E20CSE215

Introduction

some common (and terrible) approach to find a majority element in an array could be:

• running 2 nested loops

  • when iterating over the array, a nested loop keeps track of the count of the current element and updates the majority variable if it’s value if higher than what is stored

  • Complexity: O(n²) [Time]; O(1) [Space]
  • my subjective view: absolutely terrible.

• throwing a hashmap at it

  • as is the case that every problem can be solved ,,efficiently’’ by throwing a hashmap at it, same is the case over here.

  • In a single pass, we update the counter of the elements in the hashmap, and after that we iterate through all the keys in the hashmap and pick the one which has the higher count

  • Complexity: O(n) [Time]; O(n) [Space]
  • my subjective view: eh. It’s a hashmap. good enough

How Moore’s Voting Algorithm sweeps the stage

source for this amazingly intuitive graphic: Wikipedia

Throughout the dry run i will be refferring this image, cuz you just can not understand this algorithm without staring at this graphic for minutes trying to absorb it in.
Such is the magnificence of this technique

The highly abstracted idea of how it works:

“same elements get their “vote” incremented. Different elements get it’s vote decremented.”

when the vote reaches 0, we assume the next element as the majority and increase it’s count. By the end of the first pass, if vote of the majority element is greater than or equal to 2, it’s a majority otherwise there is no majority”

The main idea is that how you would count votes manually but with some “clever” optimisations:

• Let’s say that the elements in the array are “candidates”, and their count is their “vote”.

• so when iterating through the array if we encounter the same candidate as stored in our variable, it’s count goes up.

• if we encounter a different candidate the the stored candidate’s votes decrement by one.

• when the vote of a candidate drops to zero, we know that it is not in the majority so we can pick the next candidate as the assumed majority and continue this sequence.

• By the end of the iteration we will know if there is a majority in the array and which element, or no majority

Dry Run

[I have placed the image again at the bottom for easy & convenient reference]

• We start by picking the first element: the blue circle 🔵 as the assumed majority candidate and increase it’s count
• since the second element is also a blue circle 🔵, we increase 🔵’s vote by +1 which becomes 2
• the third element is a red square (🟥) which is != 🔵, so we decrement 🔵’s count to 1

• We repeat this sequence until we encounter the star ⭐ at index 5 (zero-indexed array).

  since 🔵 != ⭐, we decrease the assumed-majority element’s count by -1 which makes 🔵’s count to 0.

• As the next element is a ⭐, so instead of decrementing 🔵 to negative one, we switch our assumed-majority to ⭐ and increment it’s count to 1
• During the next 3 indexes (7, 8, 9) all 3 of those elements are 🟥 and following the process of earlier, ⭐’s count was decremented to 0 and instead of turning it negative, we pick the next element as the assumed-majority.
• now running the iteration mentally we notice that 🟥’s count is increasing — which it should be because 🟥 is the majority here — and reaches the count of 4 at the end of the iteration.

Since the count is 4 (and not 0 or 1) we can safely say that 🟥 is the majority in this array

Observations

we know that 🟥 is the majority in the array here.

But during the beggining it looked like 🔵 was becoming the majority, but due to the plain and blatantly simple logic of this algorithm, the actual majority of the array took over and had it’s count as the max

There’s just nothing else for me to say how it works, as for me it’s like explaining “why does a cat act like a cat?”/”how does a cat know how to cat”, which I’m very terrible at explaining

clik me

yes. terrible at explaining both things: 1) how do cats know how to cat and 2) explaining obvious stuff.
sorey

_{If the below part is a blank page, please disable your adblock extension for this site, or lower your privacy shield or allow youtube-nocookie.com to load}

Complexity

This chad algorithm takes O(n) Time complexity, and O(1) Space complexity

Pseudocode

    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

Python code

# generate a random array
import random
array = [random.randint(0, 5) for i in range(10)]
print(array)

assumed_majority = None
count = 0
for num in array:
    if count == 0:
        assumed_majority = num
        count += 1
    elif assumed_majority == i:
        count += 1
    else:
        count -= 1

if count > 0:
    print(assumed_majority)
else:
    print("no majority")

---

written by: E20CSE215