[Majority Element] (https://leetcode.com/problems/majority-element/description/)

Problem

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.

Solution

Brute Force Solution Using HashMap: O(n) time and O(n) space

public class Solution {
    public int majorityElement(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) map.put(num, map.getOrDefault(num, 0) + 1);
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if (entry.getValue() > nums.length / 2) return entry.getKey();
        }
        return 0;
    } 
}

Solution Using Sort: O(nlgn) time and O(1) space

public class Solution {
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length / 2];
    }
}

Boyer-Moore Majority Vote Algorithm: O(n) time and O(1) space

public class Solution {
    public int majorityElement(int[] nums) {
        int res = -1, count = 0;
        for (int num : nums) {
            if (count == 0) {
                count++;
                res = num;
            } 
            else if (num == res) count++;
            else count--;
        }
        return res;
    }
}

Analysis

This is a typical problem to find the majority element
There are three solutions listed above optimizing the time and space use