Majority element II

Link: https://leetcode.com/problems/majority-element-ii/

Solution:

Topics: Boyer-Moore voting

Intuition
This is a very tricky twist on the classic Majority element problem. Basically the twist is now which elements appear at more than n/3 times. The key insight is understanding that there can be at most 2 elements that appear more than n/3 times. Why?

Because in the best case that n is divisible by 3, you would have 3 partitions of exactly n/3 length. For an element to appear more than n/3 times, it would have to eat into at least one partition. So in the best case, you could have two homogenous partitions that can both eat into the third partition to reach n/3 elements.

But how do we modify the Majority element algorithm to work with n/3? The idea is to use two candidates and two counts, but the key here is in disallowing them to overwrite one another or take the same value.

Implementation

def maj_elementII(nums):
	cand1, cand2 = None, None
	count1, count2 = 0, 0
	
	for num in nums:       
		if num == cand1:     #fold all the logic into a single conditional
			count1 += 1      #to ensure no interference between the pairs
		elif num == cand2:   #of variables
			count2 += 1
		elif count1 == 0:
			cand1 = num
			count1 = 1
		elif count2 == 0:
			cand2 = num
			count2 = 1
		else:
			count1 -= 1
			count2 -= 1
 
	res = []                         #validate the candidates
	for cand in (cand1, cand2):
		if cand is not None:
			count = 0
			for num in nums:
				if num == cand:
					count += 1
			if count > len(nums) // 3:
				res.append(cand)
	return res
		
#time: o(n)
#memory: o(1)

Review 1
Very tricky problem, with very tricky logic. Even the order of the conditions matter! First two condition should be the increments, second two should be the reassignments, and the last one will be the decrement condition (decrement both count1 and count2).

Some edge cases:

1. if cand1 == cand2 return only one
2. validate the algorithm with a second pass

review
hard