229.md

229. Majority Elements II

Description

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.

Thinking Process

1. One important thing to take note of is that there are at most 2 majority elements in the array.
2. Define two counters and targets, interate through the array, modify the counters and targets as we did in majority element I.
3. At the end of the loop, check if the two targets appear more than n/3 times. If so, add them to the result

Code

public class Solution {
    public List<Integer> majorityElement(int[] nums) {
        List<Integer> res = new LinkedList<>();
        if(nums.length == 0)
            return res;
        int counter1 = 0;
        int counter2 = 0;
        int target1 = nums[0];
        int target2 = nums[0];
        
        for(int num : nums){
            if(num == target1){
                counter1++;
            }
            else if(num == target2){
                counter2++;
            }
            else if(counter1 == 0){
                counter1 = 1;
                target1 = num;
            }
            else if(counter2 == 0){
                counter2 = 1;
                target2 = num;
            }
            else{
                counter1--;
                counter2--;
            }
        }
        
        counter1 = 0;
        counter2 = 0;
        
        for(int num : nums){
            if(num == target1)
                counter1++;
            else if(num == target2)
                counter2++;
        }
        if(counter1 > nums.length / 3)
            res.add(target1);
        if(counter2 > nums.length / 3)
            res.add(target2);
        return res;
    }
}

Complexity

1. Time complexity is O(n) as the array is scanned twice
2. Space complexity is O(1) as no additional data structures are used