LeetCode - Majority Element

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

Example 1:

Input: [3,2,3] Output: 3

Example 2:

Input: [2,2,1,1,1,2,2] Output: 2

Solution

We can count frequency for the all elements and create a map of it. Iterate frequency map and select top most frequency element.

Code


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

public class MajorityElements {

	public int majorityElement(int[] nums) {

		Map<Integer, Integer> map = new HashMap<>();

		for (int num : nums) {
			map.put(num, (map.getOrDefault(num, 0) + 1));
		}

		int length = nums.length / 2, result = Integer.MIN_VALUE, freq = Integer.MIN_VALUE;

		for (int key : map.keySet()) {
			if (map.get(key) >= length && map.get(key) >= freq) {
				freq = map.get(key);
				result = key;
			}
			;
		}

		return result;
	}

	public static void main(String[] args) {
		int[] nums= {2,2,1,1,1,2,2};
		MajorityElements mjOnj=new MajorityElements();	
		System.out.println(mjOnj.majorityElement(nums));
	}

}