Majority Element II

NeetCode: Majority Element II · LeetCode: 229. Majority Element II · Difficulty: Medium

Given an integer array nums of size n, return all elements that appear more than n / 3 times (integer division). Aim for O(n) time and O(1) space.

Example

Text

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

Brute force: count every value

Count occurrences with a HashMap<Integer, Integer> (merge(x, 1, Integer::sum) adds 1 to the count, starting from 1 when the key is new) and keep the values whose count is greater than n / 3. Linear time, but it needs O(n) extra space in the worst case.

Java

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Solution {
    public List<Integer> majorityElement(int[] nums) {
        Map<Integer, Integer> count = new HashMap<>();
        for (int x : nums) {
            count.merge(x, 1, Integer::sum);
        }
        List<Integer> res = new ArrayList<>();
        for (Map.Entry<Integer, Integer> e : count.entrySet()) {
            if (e.getValue() > nums.length / 3) {
                res.add(e.getKey());
            }
        }
        Collections.sort(res); // HashMap order is unspecified; any order is valid, sorted for a stable printout
        return res;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.majorityElement(new int[]{3, 2, 3}));
        System.out.println(s.majorityElement(new int[]{1}));
        System.out.println(s.majorityElement(new int[]{1, 1, 1, 3, 3, 2, 2, 2}));
        System.out.println(s.majorityElement(new int[]{}));
    }
}

Output

[3]
[1]
[1, 2]
[]

Time: O(n). Space: O(n).

Optimal: Boyer-Moore voting with two candidates

At most two values can appear more than n / 3 times (three such values would need more than n elements). Keep two candidates with counters. For each number: if it equals a candidate, bump that counter; otherwise if a counter is zero, adopt the number as that candidate; otherwise decrement both counters. A decrement removes three distinct values at once (the current one and one copy of each candidate), and a value occurring more than n / 3 times cannot be fully cancelled by such triples, so every true answer survives as a candidate.

Survivors are only candidates, not guaranteed answers, so a second pass counts each one and keeps it if the count exceeds n / 3.

Java

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Solution {
    public List<Integer> majorityElement(int[] nums) {
        int c1 = 0, n1 = 0;
        int c2 = 0, n2 = 0;
        for (int x : nums) {
            if (n1 > 0 && x == c1) {
                n1++;
            } else if (n2 > 0 && x == c2) {
                n2++;
            } else if (n1 == 0) {
                c1 = x;
                n1 = 1;
            } else if (n2 == 0) {
                c2 = x;
                n2 = 1;
            } else {
                n1--;
                n2--;
            }
        }
        int limit = nums.length / 3;
        int count1 = 0, count2 = 0;
        for (int x : nums) {
            if (n1 > 0 && x == c1) {
                count1++;
            } else if (n2 > 0 && x == c2) {
                count2++;
            }
        }
        List<Integer> res = new ArrayList<>();
        if (n1 > 0 && count1 > limit) {
            res.add(c1);
        }
        if (n2 > 0 && count2 > limit) {
            res.add(c2);
        }
        Collections.sort(res);
        return res;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.majorityElement(new int[]{3, 2, 3}));
        System.out.println(s.majorityElement(new int[]{1}));
        System.out.println(s.majorityElement(new int[]{1, 1, 1, 3, 3, 2, 2, 2}));
        System.out.println(s.majorityElement(new int[]{}));
    }
}

Output

[3]
[1]
[1, 2]
[]

Time: O(n) (two passes). Space: O(1).

The n1 > 0 guards matter: a counter of zero means the candidate slot is empty, so a stale candidate value must not match a new number. The int counters never overflow, because they are at most n. The two candidates are always distinct, because a number equal to c1 is handled before the empty-slot branches.