LeetCode OJ | Majority Element Problem Solution

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

My Solution:

At first I was thinking they were asking for the mode of the set, but then I realized that they also included the stipulation that the majority element has to appear more than n/2 times. Not exactly the mode. This was my first solution:

# Set variables:
maxValue = None
barrier = len(num)/2
numDict = {}
    	

for x in range(0, len(num)):
	if num[x] in numDict:
		numDict[num[x]] += 1
    	else:
    		numDict[num[x]] = 1
    	
for y in numDict.keys():
	if numDict[y] == max(numDict.values()) and numDict[y] > barrier:
		maxValue = y	
    	
if maxValue is None:
	return False
else:
	return maxValue

So this code is pretty straightforward but also slow; essentially a brute force solution. I create an empty dictionary and run a for loop against all the entries in the num array. If that number is not in the dictionary as a key, then I add it with an associated value of 1. If the key is in the dictionary then I increment the key’s value by 1. Basically I’m counting the number of times every value is showing up, then finding which total is the highest.

Then once we have the count for all the numbers in the array, I fun a for loop on the dictionary this time. Now I’m going through all of the key values and seeing if the value associated with it is the maximum AND if it’s greater than the barrier (which is n/2). If there is a key that meets these criteria then it is associated with the maxValue variable which is later returned! Like I said, it’s been a while since I’ve used Python so my code isn’t the prettiest or most efficient in the world- but it works.

Second Method:

But this method isn’t the best. Like I said above, it’s basically a brute force method. When I solved the problem, though, they provided me with some clues for other solutions which could work. One that intrigued me was called Moore’s Voting Algorithm. Remember how the majority element had to be greater than n/2? Well, that’s what this algorithm takes advantage of. Check out this site for a bit of background. Essentially this algorithm chooses the first item in the array and sets a ‘counter’ to 1, then it moves on to the next element. If the next element is the same then it increases the counter by 1, else it decrements it by 1. If there is a majority element in the set then at the end of the function that element will be set while the counter has a value greater than 0! Take a look at this code for a bit more information:

# Set variables:
count = [None,0]

#Run it
for i in num:
	if count[1] == 0:
		count[1] = 1
		count[0] = i
	elif count[1] > 0:
		if count[0] == i:
			count[1] += 1
		else:
			count[1] -= 1
	
if count[1] <= 0:
	return False
else:
	return count[0]

I did it slightly differently, where the counter and the number are both part of a two item array. It’s essentially: [value, counter]. But it works! And though it doesn’t appear to run any faster than my previous algorithm, it’s definitely a bit more elegant.

Final Thoughts:

I think that Moore’s Voting Algorithm could be manipulated to find other majority elements where n/2 is not necessarily the barrier. For instance, what if the question was reworded to say that a majority element was a simple majority? Like in the array [2, 2, 2, 5, 5, 8, 8] the number 2 would not be the majority element in the question above but if this were a simple majority then it would be! There has to be a way to change the increment/decrement values as a function of the length of the array to factor this into play. Hmm, I’ll have to think about that a bit more. Until then, happy coding!