Majority Element II

MEDIUM

Description

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 * 10⁴
-10⁹ <= nums[i] <= 10⁹

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

Approaches

Checkout 3 different approaches to solve Majority Element II. Click on different approaches to view the approach and algorithm in detail.

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.

Algorithm

Initialize an empty result list and a set to track processed elements
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
Return result list

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.

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;
}

Complexity Analysis

Time Complexity: O(n²) where n is the length of the array as we need two nested loopsSpace Complexity: O(1) excluding the space used for output

Pros and Cons

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

Code Solutions

Checking out 4 solutions in different languages for Majority Element II. Click on different languages to view the code.

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();
    }
}

Video Solution

Watch the video walkthrough for Majority Element II

Algorithms:

Sorting

Patterns:

Counting

Data Structures:

ArrayHash Table

Companies:

Accenture |Atlassian |Salesforce |Zenefits |