Majority Element

NeetCode: Majority Element · LeetCode: 169. Majority Element · Difficulty: Easy

Given an array nums of size n, return the majority element: the one that appears more than n / 2 times. You may assume it always exists.

Example

Text

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

Brute force: count every element

For each element, scan the whole array to count its occurrences; return the first that exceeds n / 2.

Java

class Solution {
    public int majorityElement(int[] nums) {
        int n = nums.length;
        for (int x : nums) {
            int count = 0;
            for (int y : nums) {
                if (y == x) {
                    count++;
                }
            }
            if (count > n / 2) {
                return x;
            }
        }
        return -1; // not reached: a majority element is guaranteed
    }
}

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[]{2, 2, 1, 1, 1, 2, 2}));
        System.out.println(s.majorityElement(new int[]{7}));
    }
}

Output

3
2
7

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

Better: hash map of counts

Count occurrences in one pass with a HashMap<Integer, Integer>, returning as soon as any count passes n / 2. merge(x, 1, Integer::sum) inserts 1 for a new key or adds 1 to the stored count, and returns the new count. Sorting and returning nums[n / 2] is an O(n log n) alternative, since the majority element must cover the middle position.

Java

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

class Solution {
    public int majorityElement(int[] nums) {
        int n = nums.length;
        Map<Integer, Integer> counts = new HashMap<>();
        for (int x : nums) {
            int c = counts.merge(x, 1, Integer::sum); // merge returns the new count
            if (c > n / 2) {
                return x;
            }
        }
        return -1; // not reached: a majority element is guaranteed
    }
}

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[]{2, 2, 1, 1, 1, 2, 2}));
        System.out.println(s.majorityElement(new int[]{7}));
    }
}

Output

3
2
7

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

Optimal: Boyer-Moore voting

Keep a candidate and a count. When count is 0, adopt the current number as the candidate. Then add 1 if the number equals the candidate, else subtract 1. Every decrement cancels one candidate vote against one different element; since the majority element outnumbers all others combined, it cannot be fully cancelled and is the candidate at the end. This relies on the majority element existing (as guaranteed); otherwise a second pass to verify would be needed.

num	candidate	count
2	2	1
2	2	2
1	2	1
1	2	0
1	1	1
2	1	0
2	2	1

Java

class Solution {
    public int majorityElement(int[] nums) {
        int candidate = 0;
        int count = 0;
        for (int x : nums) {
            if (count == 0) {
                candidate = x;
            }
            if (x == candidate) {
                count++;
            } else {
                count--;
            }
        }
        return candidate;
    }
}

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[]{2, 2, 1, 1, 1, 2, 2}));
        System.out.println(s.majorityElement(new int[]{7}));
    }
}

Output

3
2
7

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