Majority Element

Given an array of n elements, return the majority element: the value that appears more than n / 2 times. Return OptionalInt.empty() if there isn't one. OptionalInt is a container that holds either one int or nothing. This isn't the same as the most frequent value: in [1, 1, 2, 3], 1 is the most frequent but not a majority.

LeetCode: 169. Majority Element (which guarantees a majority exists)

Example

Text

Input:  [3, 9, 1, 3, 5, 3, 3]    Output: 3   (4 of 7)
Input:  [8, 8, 8, 8, 8, 10, 10]  Output: 8
Input:  [1, 1, 2, 3]             Output: empty

Brute force: count each element

Java

import java.util.OptionalInt;

public class Main {
    static OptionalInt majority(int[] nums) {
        for (int x : nums) {
            int count = 0;
            for (int y : nums) {
                if (y == x) count++;
            }
            if (count > nums.length / 2) return OptionalInt.of(x);
        }
        return OptionalInt.empty();
    }

    public static void main(String[] args) {
        System.out.println(majority(new int[]{3, 9, 1, 3, 5, 3, 3}) + " " + majority(new int[]{8, 8, 8, 8, 8, 10, 10}) + " " + majority(new int[]{1, 1, 2, 3}));
    }
}

Output

OptionalInt[3] OptionalInt[8] OptionalInt.empty

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

Better: count in a HashMap

Count every value, and stop as soon as one count passes n / 2. merge(x, 1, Integer::sum) adds 1 to the count of x, or stores 1 when x is new.

Java

import java.util.HashMap;
import java.util.Map;
import java.util.OptionalInt;

public class Main {
    static OptionalInt majority(int[] nums) {
        Map<Integer, Integer> counts = new HashMap<>();
        for (int x : nums) {
            int count = counts.merge(x, 1, Integer::sum);
            if (count > nums.length / 2) return OptionalInt.of(x);
        }
        return OptionalInt.empty();
    }

    public static void main(String[] args) {
        System.out.println(majority(new int[]{3, 9, 1, 3, 5, 3, 3}) + " " + majority(new int[]{8, 8, 8, 8, 8, 10, 10}) + " " + majority(new int[]{1, 1, 2, 3}));
    }
}

Output

OptionalInt[3] OptionalInt[8] OptionalInt.empty

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

Optimal: Boyer-Moore voting

Pair up each occurrence of the majority value with a different value and cancel both out. Because the majority has more than half the elements, some of its occurrences are always left over.

In one pass, keep a candidate and a count. When count is 0, take the current element as the new candidate. A matching element increments count; a different one decrements it (cancels a pair).

x	3	9	1	3	5	3	3
candidate	3	3	1	1	5	5	3
count	1	0	1	0	1	0	1

The candidate is the majority if one exists. When the input might have no majority, a second pass confirms the count.

Java

import java.util.OptionalInt;

public class Main {
    static OptionalInt majority(int[] nums) {
        int candidate = 0;
        int count = 0;
        for (int x : nums) {
            if (count == 0) candidate = x;
            if (x == candidate) count++;
            else count--;
        }
        int occurrences = 0;
        for (int x : nums) {
            if (x == candidate) occurrences++;
        }
        return occurrences > nums.length / 2 ? OptionalInt.of(candidate) : OptionalInt.empty();
    }

    public static void main(String[] args) {
        System.out.println(majority(new int[]{3, 9, 1, 3, 5, 3, 3}) + " " + majority(new int[]{8, 8, 8, 8, 8, 10, 10}) + " " + majority(new int[]{1, 1, 2, 3}));
        System.out.println(majority(new int[]{}));
        System.out.println(majority(new int[]{1, 1, 2, 2}));
    }
}

Output

OptionalInt[3] OptionalInt[8] OptionalInt.empty
OptionalInt.empty
OptionalInt.empty

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

Edge cases

No majority: the verification pass returns OptionalInt.empty(); without it, the candidate would be an arbitrary value.
Exactly half ([1, 1, 2, 2]): not a majority, because it needs more than n / 2.
Empty array: OptionalInt.empty().