Leetcode 169. Majority Element

Clarification

Okay, so first I’ll restate the problem to make sure I understand it correctly.

We are given an integer array nums, and we need to return the majority element, meaning the element that appears more than 50%. And the problem guarantees that such an element always exists, which also means it won't be an empty array.

For example, if nums = [3,2,3], the answer is 3, because it appears twice out of three elements.

What is the most important value of the problem? is it time or space?

Brute-force Approach

One approach is to use a hash map to count frequencies of each element during the loop of the array. That gives us O(n) time, but it uses O(n) space.

Another approach is to sort the array first and then find the most frequent element while looping over the sorted array. The time complexity will increase to O(nlogn) but it doesn't need extra space.

Optimized Approach

The optimal approach here is Boyer-Moore Voting Algorithm. The idea is: since the majority element appears more than the half, it should be able to “cancel out” all other elements and still remain as the final candidate, like the Shisen-sho game. But instead of connecting the same mahjong tiles, we do a cancellation when there is a difference here.

So what I'll do is to repeatedly cancel different elements against each other. I track a candidate and a vote count. Matching elements increase the count, non-matching elements decrease it by one, and whenever the count reaches zero I pick a new candidate. After one loop, the surviving candidate must be the majority element. This gives O(n) time and O(1) space.

Code

class Solution {
    public int majorityElement(int[] nums) {
        int candidate = 0, vote = 0;

        for (int num : nums) {
            if (vote == 0)          candidate = num;

            if (candidate == num)   vote++;
            else                    vote--;
        }

        return candidate;
    }
}

Follow-up

One follow-up I would mention is: if the majority element is not guaranteed, then after finding the candidate, I would do a second pass to verify its frequency is actually greater than the half.