Moore Voting Algorithm
If you have an array of votes and want to find the candidate who got more than half the votes, you can use Moore's Voting Algorithm. It finds the majority element (element appearing more than n/2 times) in O(n) time and O(1) space.
The algorithm works in two passes:
- Candidate selection: Pair up different elements, cancel them out.
- Verification: Count occurrences of candidate to ensure it's majority.
Java implementation:
public static int majorityElement(int[] nums) {
// Phase 1: Find candidate
int candidate = 0, count = 0;
for (int num : nums) {
if (count == 0) {
candidate = num;
count = 1;
} else if (num == candidate) {
count++;
} else {
count--;
}
}
// Phase 2: Verify candidate
count = 0;
for (int num : nums) {
if (num == candidate) count++;
}
if (count > nums.length / 2) return candidate;
return -1; // no majority
}
Example: [3, 3, 4, 2, 3, 3, 3] → majority element is 3 (appears 5 times).
Two Minute Drill
- Moore's voting algorithm finds majority element (more than n/2) in O(n) time, O(1) space.
- Two phases: candidate selection and verification.
- Candidate selection cancels different elements; the surviving one is potential majority.
- Useful for problems where we need to find element appearing more than floor(n/2) times.
Need more clarification?
Drop us an email at career@quipoinfotech.com