Moore's Voting Algorithm
Definition:
Moore's Voting Algorithm is an efficient algorithm to find the majority element in an array. A majority element is defined as the element that appears more than N/2 times in the array, where N is the size of the array. The algorithm operates in linear time and uses constant space, making it optimal for this problem.
Characteristics:
-
Two-Pass Algorithm:
The algorithm works in two passes:- In the first pass, it finds a candidate for the majority element.
- In the second pass, it confirms whether the candidate is indeed the majority element.
-
Linear Time Complexity:
The algorithm runs in time, where N is the number of elements in the array. -
Constant Space Complexity:
It only requires a few extra variables, resulting in space complexity.
Video Explanation

Time Complexity:
-
Best Case:
The algorithm processes each element once during both passes. -
Average Case:
It consistently runs in linear time for any arrangement of elements. -
Worst Case:
Regardless of the input distribution, the time complexity remains linear.
Space Complexity:
- Space Complexity:
The algorithm uses a constant amount of extra space.
Approach:
The algorithm follows these steps:
-
Candidate Selection:
- Initialize a variable
candidateand a countercountto zero. - Traverse the array:
- If
countis zero, set the current element ascandidateand incrementcount. - If the current element is equal to
candidate, incrementcount. - If the current element is not equal to
candidate, decrementcount.
- If
- Initialize a variable
-
Validation:
- Traverse the array again to count occurrences of
candidate. - If the count is greater than N/2, return
candidate; otherwise, there is no majority element.
- Traverse the array again to count occurrences of
C++ Implementation:
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Function to find the majority element
int majorityElement(vector<int>& nums) {
int candidate = -1, count = 0;
// First pass to find the candidate
for (int num : nums) {
if (count == 0) {
candidate = num;
count = 1;
} else if (num == candidate) {
count++;
} else {
count--;
}
}
// Second pass to confirm the candidate
count = 0;
for (int num : nums) {
if (num == candidate) {
count++;
}
}
// Check if candidate is a majority element
if (count > nums.size() / 2) {
return candidate;
} else {
return -1; // No majority element
}
}
};
int main() {
vector<int> nums = {3, 3, 4, 2, 4, 4, 2, 4, 4};
// Create an instance of Solution class
Solution sol;
// Find the majority element
int majority = sol.majorityElement(nums);
// Print the majority element
if (majority != -1) {
cout << "The majority element is: " << majority << endl;
} else {
cout << "No majority element exists." << endl;
}
return 0;
}
Related Topics
- Kadane's Algorithm: Efficient algorithm for maximum subarray sum.
- Two Pointers & Sliding Window: Techniques for subarray and window processing ().
- Dijkstra's Algorithm: Shortest path algorithm for non-negative weighted graphs ().
Test Your Understanding
Answer these 3 questions to check what you have learned.
What is the main topic of this documentation page?
What should be identified before implementing moores voting algorithm?
How is understanding of moores voting algorithm best checked?
Done with this topic? Mark it as complete to track your progress.
Was this page helpful?
Discuss this page
Have a question or spot something confusing in "Moore's Voting Algorithm"? Ask below. Backed by GitHub Discussions—maintainers receive system notifications directly.