DSA Day 72: Boyer-Moore Voting Algorithm (LeetCode 169)

📅 Date: June 23, 2026

🧠 Mood: The Evaluator 🗳️

🔥 Topic: DSA Day 72: Boyer-Moore Voting Algorithm (LeetCode 169)

📉 The Brutal Efficiency of Space Optimization

After finishing the Divide and Conquer module, I wanted to jump straight into standard tracking problems. I opened LeetCode and hit **Problem 169: Majority Element**. The requirement looks trivial: find the element that appears more than $\lfloor N/2 \rfloor$ times in an array.

If you ask a beginner, they will instantly suggest using a Hash Map. Count the frequency of every element, iterate through the map, and return the one with the highest frequency. It runs in $O(N)$ time, which passes the time constraints. But using a Hash Map takes $O(N)$ auxiliary space. When an interviewer says, **"Optimize it to $O(1)$ space without sorting,"** most people freeze. That is where the Boyer-Moore Voting Algorithm comes into play. It is a masterclass in pure, mathematical logic.

---

⚔️ The Concept of Battle and Cancellation

The intuition behind this algorithm is a ruthless battle of elimination. Imagine a room full of people belonging to different political factions. If two people from different factions pair up and knock each other out of the room, who will be left at the end?

Because the majority element appears **more than half the time**, its total headcount is greater than all the other factions combined. Even if every single minority element teams up to eliminate a majority element, the majority faction will still have survivors left standing at the end.

[Image of Boyer-Moore voting algorithm state machine flow chart tracking candidate and count status]

1. The Candidate Setup

We maintain two variables: a candidate and a count. We start iterating through the array. If the count drops to 0, it means the previous candidate was completely neutralized. We immediately select the current element as our new candidate.

2. The Vote Counter

For every element we cross, if it matches our current candidate, we increment the count (faction grows stronger). If it doesn't match, we decrement the count (one-on-one elimination). Because the true majority element occupies more than half the array space, it is guaranteed to be the final candidate standing.

---

💻 The C++ Implementation

#include <iostream>
#include <vector>
using namespace std;

int majorityElement(vector<int>& nums) {
    int candidate = 0;
    int count = 0;

    for (int num : nums) {
        // Step 1: If count is 0, pick a new candidate
        if (count == 0) {
            candidate = num;
        }

        // Step 2: Increment or decrement count
        if (num == candidate) {
            count++;
        } else {
            count--;
        }
    }

    // Note: The problem guarantees that a majority element always exists.
    // Otherwise, a second pass would be needed to verify the candidate.
    return candidate;
}

int main() {
    vector<int> nums = {2, 2, 1, 1, 1, 2, 2};
    int ans = majorityElement(nums);
    
    cout << "The Majority Element is: " << ans << endl;
    // Output: 2
    return 0;
}

By avoiding maps and sorting routines, this code operates at absolute peak efficiency: **Time Complexity is $O(N)$** and **Space Complexity is $O(1)$**. This is the exact kind of answer that satisfies strict algorithmic interviews.

---

🎯 Takeaway

Boyer-Moore is a beautiful reminder that smart mathematical shortcuts can completely eliminate memory overhead. Tomorrow, we move further down our tracking track to handle sliding windows and two-pointer tracking optimization frameworks.