DEV Community

Shigeo Kageyama
Shigeo Kageyama

Posted on

Majority Element II: 4 Hardware & C++ Insights You Won't Find in the Editorial

#programming #cpp #algorithms #leetcode

You can find hundreds of tutorials explaining the Extended Boyer-Moore Voting Algorithm. I won't bore you with that here. Instead, after solving Majority Element II (LeetCode 229), I wanted to see how far I could push the optimizations while maintaining the quality of the code. I learned a few interesting facts while doing so.
Here are four micro-optimizations and engineering trade-offs most people miss:

Insight 1: Exploiting Mathematical Guarantee using (reserve)

  • It is mathematically guaranteed that there can be at most two majority elements (element appearing > ⌊n/3⌋ times).
  • Because of this mathematical limit you can use ans.reserve(2) to allocate exactly the maximum memory required for the solution. 
vector<int> ans;
ans.reserve(2);
Enter fullscreen mode Exit fullscreen mode

Insight 2: Registers over Pointer Addresses, Memory Optimizations

  • Instead of storing the candidate(possible majorities) in the vector directly you can use separate variables.
  • Accessing vector's elements involves pointer addresses, which makes it much slower as CPU has to resolve pointer addresses on every single iteration.
  • Using local variables such as candidate1 candidate2 count1 count2 will result in faster access as these can be loaded directly on CPU registers or fast L1 cache 
int cand1 = 0, cand2 = 1;
int count1 = 0, count2 = 0;
Enter fullscreen mode Exit fullscreen mode

Insight 3: Early Exit if Candidates Dead

  • Mathematically Boyer-Moore Voting Algorithm guarantees that if an element appears more than ⌊n/3⌋ times then its final count at the end of first loop will be > 0.
  • Therefore if both the counts at the end of the loop are 0 then you can return the function entirely. 
if (count1 == 0 && count2 == 0)
    return ans;
Enter fullscreen mode Exit fullscreen mode

Insight 4: Diminishing Returns of Extra Conditions

  • If you are wondering that if a count at the end of the loop is not at least 1 then why bother checking for it then here comes the concept of trade-off between efficiency and code quality.
  • You can definitely write 3 separate conditions checking if the counts are 0 or not. 
if (count1 > 0 && count2 > 0) {
    for (const int num : nums) {
        count1 += (num == cand1);
        count2 += (num == cand2);
    }
} 
else if (count1 > 0) {
    for (const int num : nums) {
        count1 += (num == cand1);
    }
} 
else if (count2 > 0) {
    for (const int num : nums) {
        count2 += (num == cand2);
    }
}
Enter fullscreen mode Exit fullscreen mode
  • But the question is "is it worth the code bloat?" and the answer for most cases is NO unless you are writing code for HFTs, games, embedded systems. You can just skip this code bloat for simple and clean code. 
for (const int num : nums)
{
    count1 += (num == cand1);
    count2 += (num == cand2);
}
Enter fullscreen mode Exit fullscreen mode
  • This is nearly as fast but with clearly less amount of code.
  • Of course you can also rely on compiler optimizations by writing the conditions inside the loop, which will be expanded by the compiler. Like this: 
for (const int num : nums) {
    if (surviving_count1 > 0) count1 += (num == cand1);
    if (surviving_count2 > 0) count2 += (num == cand2);
}
Enter fullscreen mode Exit fullscreen mode

Here's my solution to LeetCode 229: Majority Element II 

vector<int> majorityElement(const vector<int> &nums)
{
    vector<int> ans;
    ans.reserve(2);
    int majority = nums.size() / 3;
    int cand1 = 0, cand2 = 1;
    int count1 = 0, count2 = 0;

    for (const int num : nums)
    {
        if (num == cand1)
            count1++;
        else if (num == cand2)
            count2++;
        else if (count1 == 0)
        {
            cand1 = num;
            count1 = 1;
        }
        else if (count2 == 0)
        {
            cand2 = num;
            count2 = 1;
        }
        else
        {
            count1--;
            count2--;
        }
    }

    /* If count1 and count2 are 0 by the end of the loop,
       there is no majority element,
       they may be = ⌊n/3⌋ but not > ⌊n/3⌋ i.e. <= ⌊n/3⌋*/
    if (count1 == 0 && count2 == 0)
        return ans;

    count1 = 0;
    count2 = 0;
    for (const int num : nums)
    {
        count1 += (num == cand1);
        count2 += (num == cand2);
    }

    if (count1 > majority)
        ans.push_back(cand1);
    if (count2 > majority)
        ans.push_back(cand2);

    return ans;
}
Enter fullscreen mode Exit fullscreen mode

Let's Connect!

I'm a rookie dev and an explorer who loves breaking things down to see how they work under the hood. I am always learning and experimenting across different domains. If you spot any mistakes, have feedback, or know a better way to approach this, please let me know in the comments. I'd love to learn from you!

Top comments (0)