229. Majority Element II

Problem Statement

Pattern:

---

Solution

public List<Integer> majorityElement(int[] nums) {
	int count1 = 0, count2 = 0, major1 = -1, major2 = -1;
	
	// get major1 and major2
	for (int num : nums) {
		if (num == major1) count1++;
		else if (num == major2) count2++;
		else if (count1 == 0) {
			major1 = num;
			count1 = 1;
		} else if (count2 == 0) {
			major2 = num;
			count2 = 1;
		} else {
			count1--;
			count2--;
		}
	}
	
	// check count of major1 and major2
	count1 = count2 = 0;
	for (int num : nums)
		if (num == major1) count1++;
		else if (num == major2) count2++;
	
	// add majors to result
	List<Integer> res = new ArrayList<>();
	if (count1 > nums.length / 3) res.add(major1);
	if (count2 > nums.length / 3) res.add(major2);
	
	// return result
	return res;
}

Concept

Checkout the concept in 169. Majority Element first. Here the only difference is, there can only be 2 majority elements max. Why?

n=9, for an element to be a majority element it has to occupy, atleast n/3 +1 spaces (more than n/3 times so 4 spaces

lets say m1 = 13 is the first majority element that appears the minimum of 4 times. m2 = 25 is the second majority element that appears the minimum of 4 times.

So far 8 out of 9 spaces have been occupied. so as you can see… it is physically impossible to have a 3rd majority element.

now we just need to track 2 majority elements instead of one, track their counts, and reset them with a new one when their counts reach zero