This is a short, bite-sized algorithm since I’m writing this on my phone in a free class. Soo. Let’s get on with it!

Consider the question, “Given an array of n elements, find out which number occurs more than n/2 number of times, if any. If none, print -1.”

Catch is, do it in O(n) time and O(1) additional space.

First, let’s discuss other potential (but worse) solutions. Feel free to skip ahead to the section titled “Moore’s voting algorithm” if you want to skip to the action.

O(n^2) time and O(1) space approach

Now, let’s go through the naive solution -

The algorithm here is straightforward -

  • Declare two integers - answer, answer_frequency
  • Run a nested loop iterating over all elements, for every element.
  • Find if any element occurs more than n/2 number of times.
  • If yes, break out and print accordingly.
  • Else, print -1.

Simple and clear. But we want better.

O(nlogn) time and O(1) space approach

This approach is simple too.

It goes as follows -

  • Sort the array (either ascending or descending.)
  • Find the element that repeats continuously more than n/2 number of times.
  • Print element, else print -1.

Sorting the array in-place uses O(1) additional space and using a good sorting algorithm (merge sort or introsort) should get you an O(nlogn) time complexity.

But let’s do even better.

O(n) time and O( max(A) ) space approach

Now, lets say that we knew the values of the elements in the array are less than 100,000.

Yay! This means we can hash them in a direct address table!

  • Create a hash table freq[] where freq [x] stores the frequency of the number x.
  • Iterate over the array freq and check if any freq[ i ] exceeds n/2.
  • Print the element that does so, else print -1.

Of course, this depends on the values in the array so it’s fairly risky to apply it when you don’t know the upper bound on the elements.

Let’s do even better.

Moore's Voting Algorithm - O(n) time and O(1) space approach

Alright, let’s top it all. Mathematically it’s easy to see that to even solve a problem like this, you’re required to at least see all elements in the array at least once.

Therefore you cannot have a better time complexity than a linear complexity here.

This is the best solution.

Let’s dive in.

The algorithm is as follows -

  • Declare two integers - majority_index and count
  • Assign majority_index to 0 and count to 1. (What's happening here is that majority_index always stores the index of the majority element in the array, and the count variable keeps track of this number's frequency. Now we run a loop, from index 1 to n-1 (0-based indexing)
  • Now there are two cases -
    • Case 1: A[ current_index ] = A[ majority_index ] in which case we simply increment the count variable as our expected majority number has occurred once more.
    • Case 2: A[ current_index ] != A[ majority_index ] where we decrement the count variable by one as another variable seems to have occurred while we expected our majority element to have occurred.
  • Now at every iteration of our loop, after these 2 cases we check if count has equaled zero.
  • If it has equaled zero, we update majority_index to the current_index and update count as 1. As if we're assuming this new current number could be the majority element.
  • Now that we're done by our probable element, we re-iterate over the array to confirm its count exceeding n/2

And that’s it! At the very end of the loop, if counter exceeds n/2, print A[majority_index] else print -1.

The implementation of this algorithm (in Python) is as follows -

#Phase 1: finding a probabilistic majority element

majority_index=0
count=1
for i in range(1,n):
     if A[i]==A[majority_index]:
          count+=1
     else:
          count-=1
     if count==0:
          majority_index=i
          count=1

#Phase 2: verifying the majority element
count=0
for i in range(n):
     if A[i]==A[majority_index]:
          count+=1

print(A[majority_index]) if count>=(n>>1) else print(-1)

That’s how you find an element that occurs more than n/2 times in an array of length n in O(n) time and O(1) space!

Oh look at that, I managed to type this all out and the teacher’s still not started teaching. Yay!

Anywho, that’s Moore’s voting algorithm for you.

Hope it helped.

Later!

- Aditya