Array Presets
Algorithm Phases
Tug of War Mechanics
If the element matches our Candidate, we cast a +1 Vote.
If it's different, we cast a -1 Vote.
If votes drop to 0, the next element becomes the new candidate!
Live Console Log
Current Candidate
Vote Count
Moore's Voting Algorithm
Moore's Voting Algorithm (or Boyer-Moore Majority Vote) is an optimal algorithm to find the majority element in an array. A majority element is defined as an element that appears strictly more than ⌊N / 2⌋ times. It operates in $O(N)$ Time and $O(1)$ Space.
Phase 1: Finding a Candidate
Maintain a candidate and a count. If count is 0, the current element becomes the new candidate and count is set to 1. If the current element matches the candidate, increment count. Otherwise, decrement it. The surviving candidate is the only possible majority element.
Phase 2: Verifying Majority
Phase 1 only guarantees we find the majority element if one exists. If an array might not have a majority (e.g., [1, 2, 3]), the surviving candidate is just a false positive. We must do a second pass to count its actual occurrences and verify count > N/2.
Algorithm Implementation
class Solution {
public int majorityElement(int[] nums) {
// Phase 1: Find Candidate
int candidate = 0;
int count = 0;
for (int num : nums) {
if (count == 0) {
candidate = num;
}
if (num == candidate) {
count++;
} else {
count--;
}
}
// Phase 2: Verify Candidate
// Note: LeetCode 169 assumes a majority element ALWAYS exists,
// making Phase 2 optional. For LeetCode 229 (Majority Element II)
// or standard problems without that guarantee, you MUST verify.
int verifyCount = 0;
for (int num : nums) {
if (num == candidate) {
verifyCount++;
}
}
if (verifyCount > nums.length / 2) {
return candidate;
}
return -1; // No majority element found
}
}#include <vector>
using namespace std;
class Solution {
public:
int majorityElement(vector<int>& nums) {
// Phase 1: Find Candidate
int candidate = 0;
int count = 0;
for (int num : nums) {
if (count == 0) {
candidate = num;
}
count += (num == candidate) ? 1 : -1;
}
// Phase 2: Verification
int verifyCount = 0;
for (int num : nums) {
if (num == candidate) verifyCount++;
}
if (verifyCount > nums.size() / 2) return candidate;
return -1;
}
};class Solution:
def majorityElement(self, nums: List[int]) -> int:
# Phase 1: Find Candidate
candidate = None
count = 0
for num in nums:
if count == 0:
candidate = num
count += 1 if num == candidate else -1
# Phase 2: Verify Candidate
verify_count = sum(1 for num in nums if num == candidate)
if verify_count > len(nums) // 2:
return candidate
return -1