Majority Element II

Time: O(n)

Space: O(1)

Intuition

Find all elements appearing more than âŒŠn/3âŒ‹ times. At most 2 such elements exist. Use Boyer-Moore voting with 2 candidates.

Algorithm

1Maintain two candidates and their counts.
2For each element: if it matches candidate1 or 2, increment their count. If a count is 0, replace. Else decrement both.
3Verify the two candidates by counting occurrences.

Common Pitfalls

•After voting, must verify â€” candidates might not actually exceed n/3 (voting finds the POTENTIAL candidates, not guaranteed majority).

Majority Element II.java

Java

// Approach: Boyer-Moore voting for two candidates. First pass: find candidates; second pass: verify counts.
// Time: O(n) Space: O(1)
import java.util.*;

class Solution {
    // Function to find the majority elements in the array
    public List<Integer> findMajority(int[] nums) {
        Map<Integer, Integer> countMap = new HashMap<>();
        List<Integer> result = new ArrayList<>();
        int n = nums.length / 3;

        for (int num : nums)
            countMap.put(num, countMap.getOrDefault(num, 0) + 1);

        for (Map.Entry<Integer, Integer> entry : countMap.entrySet()) {
            if (entry.getValue() > n)
                result.add(entry.getKey());
        }

        return result;
    }
}

// Version 2
class Solution1 {
    public ArrayList<Integer> findMajority(int[] arr) {
        int tot = arr.length;
        ArrayList<Integer> ans = new ArrayList<>();
        TreeMap<Integer, Integer> mp = new TreeMap<>();

        for (int n : arr)
            mp.put(n, mp.getOrDefault(n, 0) + 1);

        for (int k : mp.keySet()) {
            if (tot / 3 < mp.get(k))
                ans.add(k);
        }

        return ans;
    }
}

Was this solution helpful?