Boyer-Moore Majority Vote Algori

Leetcode 169. 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.

// There is a video on youtube. There are 8 solutions to the problems.
https://www.youtube.com/watch?v=LPIvL-jvGdA

My solution using HashMap
Time complexity: O(n)
Space complexity: O(n)

class Solution {
    public int majorityElement(int[] nums) {
        HashMap<Integer, Integer> hm = new HashMap();
        int len = nums.length;
        for (int x : nums) {
            int count = 0;
            if (hm.containsKey(x)) {
                count = hm.get(x);
                hm.put(x, count + 1);
            } else {
                hm.put(x, 1);
            }
            count = hm.get(x);
            if ( count >len / 2) {
                return x;
            } 
        }
        return 0;
    }
}

Boyer-Moore Majority Vote Algorithm
Time complexity: O(n)
Space complexity: O(1)

public class Solution {
    public int majorityElement(int[] num) {

        int major=num[0], count = 1;
        for(int i=1; i<num.length;i++){
            if(count==0){
                count++;
                major=num[i];
            }else if(major==num[i]){
                count++;
            }else count--;
            
        }
        return major;
    }
}