Majority Element II

Medium
209.

Majority Element II

Majority Element II is a medium coding problem on arrays, hash table and sorting, asked in Amazon, Google and Adobe interviews.

Given an integer array nums of size n, return every element that appears more than n / 3 times, in increasing order.

At most two such elements can exist.

Example 1

Input
nums = [3,2,3]
Output
[3]
Explanation
3 appears twice out of three, and 2 > 3/3.

Example 2

Input
nums = [1]
Output
[1]

Example 3

Input
nums = [1,2]
Output
[1,2]
Explanation
Each appears once, and 1 > 2/3.

Constraints

  • 1 <= nums.length <= 40
  • -1000 <= nums[i] <= 1000

Follow-up: Can you do it in O(n) time and O(1) space? (Boyer–Moore generalises to two candidates.)

Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number[]}
 */
var majorityElement = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Majority Element II — Solution in Python, Java & C++

Majority Element II solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Majority Element II is a medium coding problem on arrays, hash table and sorting, asked in Amazon, Google and Adobe interviews.

Problem statement

Given an integer array nums of size n, return every element that appears more than n / 3 times, in increasing order.

At most two such elements can exist.

Example 1

Input: nums = [3,2,3]
Output: [3]
Explanation: 3 appears twice out of three, and 2 > 3/3.

Example 2

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

Example 3

Input: nums = [1,2]
Output: [1,2]
Explanation: Each appears once, and 1 > 2/3.

Constraints

  • 1 <= nums.length <= 40
  • -1000 <= nums[i] <= 1000

Follow-up: Can you do it in O(n) time and O(1) space? (Boyer–Moore generalises to two candidates.)

Hints for Majority Element II

  1. Hint 1

    Counting occurrences in a hash map and filtering by the n / 3 threshold is the direct O(n) solution.

  2. Hint 2

    Use a strict > comparison — exactly n / 3 occurrences does not qualify.

  3. Hint 3

    The O(1)-space version keeps two candidates with two counters, then verifies both in a second pass.

How to solve Majority Element II

Count every value and keep those whose count strictly exceeds n / 3; at most two can qualify.

Approach

  1. Tally occurrences in a map.
  2. Filter values with count > n / 3.
  3. Sort and return.

Why it works

Three values each appearing more than n / 3 times would total more than n elements, so the filter yields at most two.

Complexity

  • Time — O(n)
  • Space — O(n)

Pitfalls

  • Use a strict comparison; exactly n / 3 occurrences does not qualify.
  • Boyer–Moore with two candidates plus a verification pass gives O(1) space.

Reference solution

Python

def majorityElement(nums):
    count = {}
    for x in nums:
        count[x] = count.get(x, 0) + 1
    threshold = len(nums) / 3
    return sorted(v for v, c in count.items() if c > threshold)

Java

public static int[] majorityElement(int[] nums) {
    Map<Integer, Integer> count = new HashMap<>();
    for (int x : nums) count.put(x, count.getOrDefault(x, 0) + 1);
    List<Integer> out = new ArrayList<>();
    for (Map.Entry<Integer, Integer> e : count.entrySet()) {
        if (e.getValue() * 3 > nums.length) out.add(e.getKey());
    }
    Collections.sort(out);
    int[] res = new int[out.size()];
    for (int i = 0; i < res.length; i++) res[i] = out.get(i);
    return res;
}

C++

vector<int> majorityElement(vector<int>& nums) {
    unordered_map<int, int> count;
    for (int x : nums) count[x]++;
    vector<int> out;
    for (auto& kv : count) {
        if (kv.second * 3 > (int) nums.size()) out.push_back(kv.first);
    }
    sort(out.begin(), out.end());
    return out;
}

JavaScript

var majorityElement = function(nums) {
    const count = new Map();
    for (let i = 0; i < nums.length; i++) {
        count.set(nums[i], (count.get(nums[i]) || 0) + 1);
    }
    const out = [];
    const threshold = nums.length / 3;
    count.forEach(function(c, v) { if (c > threshold) out.push(v); });
    return out.sort(function(a, b) { return a - b; });
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets