# Majority Element II
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/majority-element-ii)
Canonical: https://scaleengineer.com/dsa/problems/majority-element-ii
**Patterns:** [Counting](https://scaleengineer.com/dsa/patterns/counting)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Hash Table
**Companies:** [Accenture](https://scaleengineer.com/companies/accenture), [Atlassian](https://scaleengineer.com/companies/atlassian), [Salesforce](https://scaleengineer.com/companies/salesforce), [Zenefits](https://scaleengineer.com/companies/zenefits), [Darwinbox](https://scaleengineer.com/companies/darwinbox)
---
## Problem
Given an integer array of size `n`, find all elements that appear more than `⌊ n/3 ⌋` times.

**Example 1:**

**Input:** nums = [3,2,3]
**Output:** [3]

**Example 2:**

**Input:** nums = [1]
**Output:** [1]

**Example 3:**

**Input:** nums = [1,2]
**Output:** [1,2]

**Constraints:**

* `1 <= nums.length <= 5 * 104`
* `-109 <= nums[i] <= 109`

**Follow up:** Could you solve the problem in linear time and in `O(1)` space?

# Approaches
## Brute Force Approach
The simplest approach is to count the frequency of each element in the array and check which elements appear more than ⌊n/3⌋ times.
**Time:** O(n²) where n is the length of the array as we need two nested loops · **Space:** O(1) excluding the space used for output
**Pros:** Simple to understand and implement; No extra space required except for output
**Cons:** Very inefficient for large arrays; Requires nested loops making it slow
### Explanation
For each element in the array, we count its frequency by comparing it with all other elements. If the frequency is greater than ⌊n/3⌋, we add it to our result list. To avoid duplicates, we can maintain a set of elements we've already processed.

```java
public List<Integer> majorityElement(int[] nums) {
    List<Integer> result = new ArrayList<>();
    Set<Integer> seen = new HashSet<>();
    int n = nums.length;
    int threshold = n / 3;
    
    for (int i = 0; i < n; i++) {
        if (seen.contains(nums[i])) continue;
        
        int count = 1;
        for (int j = i + 1; j < n; j++) {
            if (nums[j] == nums[i]) {
                count++;
            }
        }
        
        if (count > threshold) {
            result.add(nums[i]);
        }
        seen.add(nums[i]);
    }
    
    return result;
}
```
### Algorithm
1. Initialize an empty result list and a set to track processed elements
2. For each element nums[i] in the array:
   - If element is already processed, skip it
   - Count its frequency by comparing with remaining elements
   - If frequency > ⌊n/3⌋, add to result
   - Add element to processed set
3. Return result list

## HashMap Approach
We can use a HashMap to store the frequency of each element in a single pass through the array, then check which elements appear more than ⌊n/3⌋ times.
**Time:** O(n) where n is the length of the array · **Space:** O(n) to store the HashMap
**Pros:** More efficient than brute force approach; Only requires single pass through array; Easy to implement and understand
**Cons:** Requires extra space proportional to input size; Not optimal in terms of space complexity
### Explanation
We first create a HashMap to store element-frequency pairs. We traverse the array once to count frequencies, then check which elements have frequency greater than ⌊n/3⌋.

```java
public List<Integer> majorityElement(int[] nums) {
    List<Integer> result = new ArrayList<>();
    Map<Integer, Integer> countMap = new HashMap<>();
    int n = nums.length;
    int threshold = n / 3;
    
    // Count frequencies
    for (int num : nums) {
        countMap.put(num, countMap.getOrDefault(num, 0) + 1);
    }
    
    // Check which elements appear more than n/3 times
    for (Map.Entry<Integer, Integer> entry : countMap.entrySet()) {
        if (entry.getValue() > threshold) {
            result.add(entry.getValue());
        }
    }
    
    return result;
}
```
### Algorithm
1. Initialize a HashMap to store element frequencies
2. Traverse array once to count frequencies
3. Check HashMap entries for elements with frequency > ⌊n/3⌋
4. Add qualifying elements to result list

## Boyer-Moore Majority Vote Algorithm
We can use a modified version of Boyer-Moore Majority Vote algorithm to find elements appearing more than ⌊n/3⌋ times in O(n) time and O(1) space.
**Time:** O(n) where n is the length of the array · **Space:** O(1) as we only use a constant amount of extra space
**Pros:** Optimal time complexity O(n); Constant space complexity O(1); Works in two passes through the array
**Cons:** More complex to understand and implement; Requires two passes through the array
### Explanation
Since we're looking for elements appearing more than ⌊n/3⌋ times, there can be at most two such elements. We can use two counters and two candidates to keep track of potential majority elements.

```java
public List<Integer> majorityElement(int[] nums) {
    List<Integer> result = new ArrayList<>();
    if (nums == null || nums.length == 0) return result;
    
    // First pass to find candidates
    int candidate1 = nums[0], candidate2 = nums[0];
    int count1 = 0, count2 = 0;
    
    for (int num : nums) {
        if (num == candidate1) {
            count1++;
        } else if (num == candidate2) {
            count2++;
        } else if (count1 == 0) {
            candidate1 = num;
            count1 = 1;
        } else if (count2 == 0) {
            candidate2 = num;
            count2 = 1;
        } else {
            count1--;
            count2--;
        }
    }
    
    // Second pass to verify candidates
    count1 = 0;
    count2 = 0;
    for (int num : nums) {
        if (num == candidate1) count1++;
        else if (num == candidate2) count2++;
    }
    
    int threshold = nums.length / 3;
    if (count1 > threshold) result.add(candidate1);
    if (count2 > threshold && candidate1 != candidate2) result.add(candidate2);
    
    return result;
}
```
### Algorithm
1. Initialize two candidates and their counters
2. First pass: Use Boyer-Moore voting to find potential candidates
   - If current number matches either candidate, increment respective counter
   - If a counter is 0, replace that candidate
   - If neither matches and both counters > 0, decrement both counters
3. Second pass: Count actual frequencies of candidates
4. Add candidates to result if they appear more than ⌊n/3⌋ times

# Solutions
### CSharp

```csharp
public class Solution {
    public IList < int > MajorityElement(int[] nums) {
        int n1 = 0, n2 = 0;
        int m1 = 0, m2 = 1;
        foreach(int m in nums) {
            if (m == m1) {
                ++n1;
            } else if (m == m2) {
                ++n2;
            } else if (n1 == 0) {
                m1 = m;
                ++n1;
            } else if (n2 == 0) {
                m2 = m;
                ++n2;
            } else {
                --n1;
                --n2;
            }
        }
        var ans = new List < int > ();
        ans.Add(m1);
        ans.Add(m2);
        return ans.Where(m => nums.Count(n => n == m) > nums.Length / 3).ToList();
    }
}
```

### Java

```java
class Solution {
public
  List<Integer> majorityElement(int[] nums) {
    int n1 = 0, n2 = 0;
    int m1 = 0, m2 = 1;
    for (int m : nums) {
      if (m == m1) {
        ++n1;
      } else if (m == m2) {
        ++n2;
      } else if (n1 == 0) {
        m1 = m;
        ++n1;
      } else if (n2 == 0) {
        m2 = m;
        ++n2;
      } else {
        --n1;
        --n2;
      }
    }
    List<Integer> ans = new ArrayList<>();
    n1 = 0;
    n2 = 0;
    for (int m : nums) {
      if (m == m1) {
        ++n1;
      } else if (m == m2) {
        ++n2;
      }
    }
    if (n1 > nums.length / 3) {
      ans.add(m1);
    }
    if (n2 > nums.length / 3) {
      ans.add(m2);
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> majorityElement(vector<int> &nums) {
    int n1 = 0, n2 = 0;
    int m1 = 0, m2 = 1;
    for (int m : nums) {
      if (m == m1)
        ++n1;
      else if (m == m2)
        ++n2;
      else if (n1 == 0) {
        m1 = m;
        ++n1;
      } else if (n2 == 0) {
        m2 = m;
        ++n2;
      } else {
        --n1;
        --n2;
      }
    }
    vector<int> ans;
    if (count(nums.begin(), nums.end(), m1) > nums.size() / 3)
      ans.push_back(m1);
    if (count(nums.begin(), nums.end(), m2) > nums.size() / 3)
      ans.push_back(m2);
    return ans;
  }
};

```

### Python

```python
class Solution:
    def majorityElement(self, nums: List[int]) -> List[int]: n1 = n2 = 0 m1, m2 = 0, 1 for m in nums: if m == m1: n1 += 1 elif m == m2: n2 += 1 elif n1 == 0: m1, n1 = m, 1 elif n2 == 0: m2, n2 = m, 1 else: n1, n2 = n1 - 1, n2 - 1 return [m for m in [m1, m2] if nums . count(m) > len(nums) // 3]

```