Leetcode: Majority Element II

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times. The algorithm should run in linear time and in O(1) space.

Hint:

1. How many majority elements could it possibly have?
2. Do you have a better hint? Suggest it!

Understand the problem:
Since the problem suggest to use O(1) space solution, we cannot use a hash map to store the visited elements. 

How many elements could it possiblly have? Since the majority number is more than n / 3, the maximal majority elements are 2. 

So we could maintain two candidates and the counters for the candidates, respectively. The rest of the method is the same of the Moore vote algorithm. Note that we need to re-validate again at the end because it is possible that the array does not have any majority elements. 

Code (Java):

public class Solution {
    public List<Integer> majorityElement(int[] nums) {
        List<Integer> result = new ArrayList<Integer>();
        
        if (nums == null || nums.length == 0) {
            return result;
        }
        
        if (nums.length == 1) {
            result.add(nums[0]);
            return result;
        }
        
        int candidate1 = nums[0];
        int candidate2 = 0;
        
        int count1 = 1;
        int count2 = 0;
        
        for (int i = 1; i < nums.length; i++) {
            int num = nums[i];
            if (candidate1 == num) {
                count1++;
            } else if (candidate2 == num) {
                count2++;
            } else if (count1 == 0) {
                candidate1 = num;
                count1 = 1;
            } else if (count2 == 0) {
                candidate2 = num;
                count2 = 1;
            } else {
                count1--;
                count2--;
            }
        }
        
        count1 = 0;
        count2 = 0;
        
        for (int num : nums) {
            if (num == candidate1) {
                count1++;
            } else if (num == candidate2) {
                count2++;
            }
        }
        
        if (count1 > nums.length / 3) {
            result.add(candidate1);
        }
        
        if (count2 > nums.length / 3) {
            result.add(candidate2);
        }
        
        return result;
    }
}