Moore's Voting Algorithm

Ujjwal SharmaUjjwal Sharma
2 min read

Working

  1. Let the initial length be 1, because we are considering the first element as the initial element in our count.

  2. Move forward in the array and if the same element appears again, then increase the count by 1; if not, then decrease the count by 1.

  3. When the count becomes 0, change the element to the current element in the ongoing iteration.

  4. Repeat the steps from 1-3.

Code (this code is different from the reference video's code)

because leet code is throwing an error on test case 45 when we are using it

int element(vector<int> arr) {

    int length = 1; 
    int element = arr[0]; 

    //applying the algorithm:
    for (int i = 0; i < arr.size(); i++) {
        if (length == 0) {
            length = 1; // because we are considering ths element as first
            elemenent = arr[i];
        }
        else if (element == arr[i]){
             length++;
        }
        else {
            count--;
        }
    }
}

Time Complexity : O(n)

Space Complexity : O(1)

For a detailed dry run of this algorithm and an example for better understanding, you can refer to this video by Take U Forward:

Moore's Voting Algorithm Explained

Try this leetcode problem once you are done with learning

solution

Save this article to revise the algorithm in the future so that you don't need to check the video repeatedly.

All the best for your DSA journey! Let me know your feedback so that we can improve this article together.

Ujjwal Sharma

0
Subscribe to my newsletter

Read articles from Ujjwal Sharma directly inside your inbox. Subscribe to the newsletter, and don't miss out.

Written by

Ujjwal Sharma
Ujjwal Sharma