James Michael Hare

...hare-brained ideas from the realm of software development...
posts - 166 , comments - 1431 , trackbacks - 0

My Links

News

Welcome to my blog! I'm a Sr. Software Development Engineer in the Seattle area, who has been performing C++/C#/Java development for over 20 years, but have definitely learned that there is always more to learn!

All thoughts and opinions expressed in my blog and my comments are my own and do not represent the thoughts of my employer.

Blogs I Read

Follow BlkRabbitCoder on Twitter

Tag Cloud

Article Categories

Archives

Post Categories

Image Galleries

.NET

CSharp

Little Wonders

Little Wonders

vNext

Solution to Little Puzzlers–Find the Majority Element

This is the way I went about the "The Majority Element” problems. However, keep in mind there are multiple ways to solve this, so don't worry if your solution has variations and it’s entirely possible there are more efficient ways.

Feel free to suggest your solution in the comments here or in the original post, but please be respectful of others’ efforts.

A Linear-Time, Linear-Space Solution

As with so many puzzlers, there is more than one way to tackle this problem.  Let’s first consider the more straight-forward approach.

If we think about it, what we really want to do in the simplest sense, is to get a count of each element and see if an element occurs more than n/2 times (roughly speaking).

An easy way to do this would be to create a Dictionary<int, int> that would use the element as the key, and hold a count of occurrences as the value.  This would let us take a linear pass through the list to populate the Dictionary, and then one linear pass through the Dictionary to find the count (if any) > n/2.

This would give us an O(n) solution since we know that the number of items in the dictionary is <= the number of items in the sequence.  In fact, if we had foreknowledge that the range was limited (say the values ‘1’ – ‘10’) we could easily create an array to hold the counts.  However, let’s assume that is unknown and go with the dictionary:

   1: public static int? LinearTimeMajority(IEnumerable<int> sequence)
   2: {
   3:     int total = 0;
   4:     var counts = new Dictionary<int, int>();
   5:  
   6:     foreach (var item in sequence)
   7:     {
   8:         int count;
   9:         counts[item] = counts.TryGetValue(item, out count) ? ++count : 1;
  10:         ++total;
  11:     }
  12:  
  13:     var majority = counts.FirstOrDefault(p => p.Value > total / 2.0);
  14:  
  15:     return majority.Value != 0 ? majority.Key : (int?)null;
  16: }

This gives us linear time – O(n) – but also, potentially takes linear space since we may potentially need one entry in the hash for every element in the list, worst case.

A Linear-Time, Constant-Space Solution

It turns out, there is an algorithm to determine the majority element in linear time that also only takes constant space.  That is, you do not need to hold a count for every unique element.  This algorithm (the Boyer-Moore Majority Vote Algorithm) has three very simple steps:

  • Start a counter at 0 and hold a current candidate
  • For each element in the list:
    • If counter = 0, set current candidate to the element and counter to 1
    • If counter != 0, increment counter if element is current candidate, decrement if not.

Sounds simple, but why does it work?  It’s actually pretty simple.  If counter is zero, it means there isn’t a current majority, so look for a new candidate.  If current is > 1, it means that for the list so far, the candidate is a possible majority.  When you complete the list, you will be left with one candidate which will either be the majority, or no majority exists.  You can then do a simple compare against the count / 2.0 to see if the element is the majority.

Think of it this way, every time the counter becomes zero, we’re effectively throwing away the list up to that point because there is no majority in the list before us.  If there WERE, the counter would be positive because it would have to occur more times (increment) than not (decrement) to be positive.

For example, say we have the sequence: 1, 2, 2, 1, 1, 1, 2, 1, 3, 1

Let’s look at how this algorithm would play out:

Index 0 1 2 3 4 5 6 7 8 9
Value 1 2 2 1 1 1 2 1 3 1
State candidate = 1
count = 1
candidate = 1
count
= 0
candidate = 2
count
= 1
candidate = 2
count
= 0
candidate = 1
count
= 1
candidate = 1
count
= 2
candidate = 1
count
= 1
candidate = 1
count
= 2
candidate
= 1
count
= 1
candidate = 1
count
= 2

 

Notice in the two places the count goes back down to zero (indexes 1 and 3) that we determined that in those lists (so far) we had no majority, so we can start over looking for a new candidate.  However, starting at index 4, the count of 1s from that point forward remains positive because we never have enough non-1s to get us back down to zero.  Hence, 1 is our candidate majority, and we need only now count those 1s (another linear pass) to check if 1 is the majority, or if no majority exists.

Thus, the algorithm is linear complexity in time, and constant complexity in space (only need to hold a candidate and a count).  Of course, this assumes you have the ability to re-iterate over your sequence.

   1: public static int? LinearSpaceAndTimeMajority(IEnumerable<int> sequence)
   2: {
   3:     int total = 0;
   4:     int currentCount = 0;
   5:     int? current = null;
   6:  
   7:     foreach (var item in sequence)
   8:     {
   9:         if (currentCount == 0)
  10:         {
  11:             current = item;
  12:             currentCount = 1;
  13:         }
  14:         else if (current == item)
  15:         {
  16:             ++currentCount;
  17:         }
  18:         else
  19:         {
  20:             --currentCount;
  21:         }
  22:         ++total;
  23:     }
  24:  
  25:     return current.HasValue && (sequence.Count(i => i == current.Value) > total / 2.0)
  26:         ? current.Value : (int?)null;
  27: }

 

Summary

Hope you had fun with this one!  Of course, I’m sure many out there can tweak the answer for performance in various ways – but you get the point.

Have a solution that worked for you but was totally different?  I’d love to hear about it!

Stay tuned next week for the next Little Puzzler.

Print | posted on Monday, July 20, 2015 10:53 AM | Filed Under [ My Blog C# Software .NET Little Puzzlers Technology ]

Powered by: