Moore Majority Vote Algorithm [LC150]

Hello friends,

Hope you’re doing well.

Today we are going to discuss an important algo in software engineering called “Moore Majority vote”. We shall also try to implement it in C#.

Let’s first talk about background work that is done prior to this algo and then we shall understand how it’s useful.

Let’s take an example to understand what Majority element is-

The majority element is the element that appears more than ⌊n / 2⌋ times.

Example1:Input: [3,2,3], Output: 3 since 3 appears 2 times (more than 3/2 times)
Example2: Input: [2,2,1,1,1,2,2], Output: 2, since 2 appears 4 times (more than 7/2 time)

To find the solution, let’s go with different approaches.

1. Brute:

In this primary approach, we tool 2 loops to determine the majority elements. As you can see we are keeping a counter and as soon as we found an element that has appeared more than n/2 times, we are returning that element.

Here Time complexity is O(n^2) and Space O(1)

private static int GetMejorityElement(int[] nums) 
        {
            int n = nums.Length;
            int cnt;
            for (int i = 0; i < n; i++) {
                cnt  = 0;
                for (int j = 0; j < n; j++) {
                    if (nums[i] == nums[j]){
                        cnt++;
                    }
                    if (cnt > n/2) {
                        return nums[i];
                    }                   
                }                
            }
            return -1;       
        }        

2. Better:

In the previous approach time complexity is way too high and it’s generally not acceptable. Let’s optimize it to bring down the time complexity.

private static int GetMejorityElement2(int[] nums)
        {
            Dictionary<int, int> dict = [];
            int n = nums.Length;

            foreach (int i in nums) {
                if (!dict.ContainsKey(i)) {
                    dict[i] = 1;
                }
                else {
                    dict[i]++;
                }
            }
            foreach (var d in dict) { //TC: O(n log n)
                if (d.Value > (n / 2)) {
                    return d.Key;
                }
            }
            return -1;
        }

Here due to the dictionary, we improved on the time complexity and it’s now close to O(n), however space complexity has increased to O(n) due to extra container object i.e. dictionary.

3. Optimal:

Now we have come to the juncture where we can introduce Moore Majority vote algo. This algo does good job in keeping both time and space complexity low.

Here’s are the key steps in the algo-

1. pick first element
2. Traverse the array and if same element found, increase the count, if not, decrease the count
3. if in a mid way, count becomes zero, start again from the next element and repeat the step#2 until loop ends.
4. The last element who wasn’t cancelled could be the majority element if majority element exists in an array.
5. If the assumption of always having majority element exists, you don’t need to have the 2nd pass or traversal, otherwise, have a 2nd pass to get the counts of chosen element in a step#4 and if appearance is more than n/2 times, return it.

Below is the implementation for the same.

private static int GetMejorityElement3(int[] nums)
        {
            int n = nums.Length;
            int cnt  = 0;
            int ele= default;

            for (int i = 0; i<n; i++) {
                if (cnt == 0) {
                    cnt = 1;
                    ele = nums[i];
                } else if (nums[i] == ele) {
                    cnt++;
                } else {
                    cnt--;
                }
            }

            //Below step is not required, if majority element is always present in array
            cnt = 0;
            for (int i = 0; i<n; i++) {
                if (nums[i]== ele) {
                    cnt++;
                }
            }
            if (cnt > (n/2)){
                return ele;
            }
            return -1;
        }

As you can see, the time complexity is still O(n) and space complexity has came down to O(1) since we are NOT using any additional container.

Hope you’re liked the article, looking forward for your comments/ suggestions below.