169. Majority Element

/**

 * 169. Majority Element

 * Given an array nums of size n, return the majority element.

 * The majority element is the element that appears more than ⌊n / 2⌋ times.

 * You may assume that the majority element always exists in the array.

 * Example 1:

 * Input: nums = [3,2,3]

 * Output: 3

 * Example 2:

 * Input: nums = [2,2,1,1,1,2,2]

 * Output: 2

*/

See solution to the problem on github here: https://github.com/zcoderz/leetcode/blob/main/src/main/java/frequent/medium/MajorityElement.java

The approach to this problem is elegant and unique. Hence, I have included it here. The approach is based on the ‘Boyer-Moore Voting Algorithm’.

The problem is simple to solve via creating a map and checking count of the elements while keeping the highest count in a variable. This solution is simpler in that it doesn’t require a map.

The logic is:

1. Iterate the elements from left to right
2. Keep a counter to signify most frequent element count and the most frequent element seen so far
3. When counter in #2 reaches 0 , reset most frequent number to current number
4. When the same number as most frequent number is seen, increase frequency in 2 by 1, otherwise decrease it by 1

Here is the code:

public int majorityElement(int[] nums) {
    int candidate = 0;
    int count = 0;
    for (int num : nums) {
        if (count == 0) {
            candidate = num;
        }
        count += num == candidate ? 1 : -1;
    }
    return candidate;
}