aarthirs

Posted on Jul 14

From LeetCode to Production: What the Boyer-Moore Voting Algorithm Taught Me

#algorithms #dsa #systemdesign #programming

Like many developers, I spend part of my free time solving LeetCode problems. Recently, I came across Majority Element II, which asks us to find all elements that appear more than ⌊n/3⌋ times.

My first instinct was the obvious one—use an unordered_map to count frequencies.

It worked.

It passed every test case.

Then I noticed the follow-up:

Can you solve it in O(n) time using O(1) extra space?

That single constraint completely changed the way I looked at the problem.

Instead of asking:

"How do I count frequencies?"

I started asking:

"How can I identify frequent elements without storing every frequency?"

That question led me to the Boyer-Moore Voting Algorithm.

🤯 The "Wait... How Does This Even Work?" Moment

At first, the algorithm honestly felt like magic.

How can you find the majority element without actually counting everything?

The answer is surprisingly elegant.

Instead of keeping track of every element, we maintain only a few potential candidates along with their counters.

Whenever we encounter:

the same candidate → increase its vote
a different number while a counter is available → make it the new candidate
a completely different number while both candidates are active → decrease both counters

Instead of counting frequencies, the algorithm lets different values cancel each other out.

Imagine every element casting a vote. Whenever two different values compete, they cancel each other's votes. By the end of the first pass, only the elements with enough "support" remain as potential candidates.

💡 Key Takeaway

One of the most elegant properties of the Boyer-Moore Voting Algorithm is:

For a problem where an element must appear more than ⌊n/k⌋ times, you only need to track k − 1 candidates.

Why?

Because there can never be k distinct elements, each occurring more than ⌊n/k⌋ times. Their combined occurrences would exceed n, which is impossible.

For Majority Element II, the threshold is ⌊n/3⌋, so there can be at most two majority elements.

That's why we only maintain:

2 candidate buckets
2 counters

instead of storing frequencies for every unique number.

🧠 The Core Idea

The heart of the algorithm looks something like this:

for (int num : nums) {
    if (num == candidate1)
        count1++;
    else if (num == candidate2)
        count2++;
    else if (count1 == 0) {
        candidate1 = num;
        count1 = 1;
    }
    else if (count2 == 0) {
        candidate2 = num;
        count2 = 1;
    }
    else {
        count1--;
        count2--;
    }
}

Notice that this doesn't guarantee the candidates are actual majority elements.

It simply identifies the most likely candidates after all possible cancellations.

That's why the algorithm performs a second pass to verify whether these candidates actually occur more than ⌊n/3⌋ times.

This two-pass approach is what allows Boyer-Moore to achieve:

Time Complexity: O(n)
Space Complexity: O(1)

🚀 Then I Started Thinking Beyond LeetCode...

Once I understood the algorithm, I realized something interesting.

The optimization wasn't just about passing an interview.

It was about thinking differently when memory is limited.

Imagine you're building a backend service processing millions of events every second.

You're monitoring:

API requests
User IDs
Search queries
Clickstream events
Network traffic

Keeping a frequency map for every unique value isn't always practical.

As the number of unique items grows, so does the memory required to store them.

Instead, modern streaming systems rely on algorithms that summarize data while using a fixed amount of memory.

The Boyer-Moore Voting Algorithm is a perfect example of this mindset.

Rather than remembering everything, it continuously filters out less significant data and preserves only the strongest candidates.

That idea appears repeatedly in large-scale systems where memory is a precious resource.

Whether it's identifying heavy hitters in a data stream, processing telemetry, or analyzing high-volume events, engineers often prefer algorithms that make intelligent trade-offs instead of storing every detail.

💭 What This Problem Actually Taught Me

Before solving this problem, I viewed algorithms as interview questions.

Now I see them as engineering decisions.

The follow-up constraint wasn't there just to make the question harder.

It was teaching an important design principle:

Sometimes the smartest solution isn't storing more information—it's figuring out what information you can safely discard.

That realization changed the way I think about optimization.

🎯 My Takeaway

If you're grinding LeetCode, don't stop once you get the green Accepted badge.

Instead, ask yourself:

Why does this optimization exist?
What real-world limitation is it solving?
Where would this idea actually be useful in production?
What trade-offs is this algorithm making?

For me, the Boyer-Moore Voting Algorithm wasn't just another optimization problem.

It became a reminder that great software engineering isn't about using more memory or writing more code.

It's about building solutions that remain efficient even when the scale grows beyond what brute force can handle.

Sometimes, one LeetCode problem can teach a system design lesson you'll carry throughout your engineering career.

Have you ever learned an interview algorithm that completely changed how you think about software engineering?

I'd love to hear your story in the comments. 👇

DEV Community