package com.thealgorithms.datastructures.hashmap.hashing;

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

/**
 * This class provides a method to find the majority element(s) in an array of integers.
 * A majority element is defined as an element that appears at least ⌊n/2⌋ times,
 * where n is the length of the array. If multiple elements qualify as majority elements,
 * they are all returned in a list.
 */
public final class MajorityElement {
    private MajorityElement() {
    }

    /**
     * Returns a list of majority element(s) from the given array of integers.
     *
     * @param nums an array of integers
     * @return a list containing the majority element(s); returns an empty list if none exist
     */
    public static List<Integer> majority(int[] nums) {
        HashMap<Integer, Integer> numToCount = new HashMap<>();
        for (final var num : nums) {
            numToCount.merge(num, 1, Integer::sum);
        }
        List<Integer> majorityElements = new ArrayList<>();
        for (final var entry : numToCount.entrySet()) {
            if (entry.getValue() >= nums.length / 2) {
                majorityElements.add(entry.getKey());
            }
        }
        return majorityElements;
    }
}