Majority Element II

229.Majority Element II

Array

Hash Table

Counting

Problem Statement:

Given an integer array nums of size n, return all elements that appear more than ⌊n/3⌋ times. The algorithm must run in linear time and use only constant extra space.

Example:

Input:

nums = [3,2,3]

→

Output:

[3]

Java Solution:

public List<Integer> majorityElement(int[] nums) {
    List<Integer> res = new ArrayList<>();
    if (nums == null || nums.length == 0) return res;
    
    // Initialize candidates and their counts
    int num1 = nums[0], num2 = nums[0]; 
    int count1 = 0, count2 = 0;
    
    // First pass: Boyer-Moore Majority Vote algorithm
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] == num1) {
            count1++;
        } else if (nums[i] == num2) {
            count2++;
        } else if (count1 == 0) {  // Replace first candidate
            num1 = nums[i];
            count1 = 1;
        } else if (count2 == 0) {  // Replace second candidate
            num2 = nums[i];
            count2 = 1;
        } else {  // Decrease both counts
            count1--;
            count2--;
        } 
    }
    
    // Second pass: Count actual frequencies of candidates
    count1 = 0;
    count2 = 0;
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] == num1) count1++;
        else if (nums[i] == num2) count2++;
    }
    
    // Check if candidates appear more than n/3 times
    if (count1 > nums.length/3) res.add(num1);
    if (count2 > nums.length/3) res.add(num2);
    
    return res;  
}

Python Solution:

def majorityElement(self, nums: List[int]) -> List[int]:
    if not nums:
        return []
        
    # Initialize candidates
    num1 = num2 = nums[0]
    count1 = count2 = 0
    
    # First pass: find candidates
    for num in nums:
        if num == num1:
            count1 += 1
        elif num == num2:
            count2 += 1
        elif count1 == 0:
            num1, count1 = num, 1
        elif count2 == 0:
            num2, count2 = num, 1
        else:
            count1, count2 = count1 - 1, count2 - 1
            
    # Second pass: count frequencies
    count1 = count2 = 0
    for num in nums:
        if num == num1:
            count1 += 1
        elif num == num2:
            count2 += 1
            
    result = []
    n = len(nums)
    if count1 > n//3: result.append(num1)
    if count2 > n//3: result.append(num2)
        
    return result

C++ Solution:

class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {
        if(nums.empty()) return {};
        
        // Initialize candidates
        int num1 = nums[0], num2 = nums[0];
        int count1 = 0, count2 = 0;
        
        // First pass
        for(int num : nums) {
            if(num == num1) count1++;
            else if(num == num2) count2++;
            else if(count1 == 0) {
                num1 = num;
                count1 = 1;
            }
            else if(count2 == 0) {
                num2 = num;
                count2 = 1;
            }
            else {
                count1--;
                count2--;
            }
        }
        
        // Second pass
        count1 = count2 = 0;
        for(int num : nums) {
            if(num == num1) count1++;
            else if(num == num2) count2++;
        }
        
        vector<int> result;
        if(count1 > nums.size()/3) result.push_back(num1);
        if(count2 > nums.size()/3) result.push_back(num2);
        
        return result;
    }
};

Complexity:

Time: O(n) | Space: O(1)